A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface

Vincent Cohen-Addad, Arnaud de Mesmay

Given a graph $G$ cellularly embedded on a surface $\Sigma$ of genus $g$, a cut graph is a subgraph of $G$ such that cutting $\Sigma$ along $G$ yields a topological disk. We provide a fixed…