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

Given a graph $G$ cellularly embedded on a surface $\mathrm{\Sigma }$ of genus $g$, a cut graph is a subgraph of $G$ such that cutting $\mathrm{\Sigma }$ along $G$ yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any $\epsilon >0$, we show how to compute a $(1+\epsilon )$ approximation of the shortest cut graph in time $f(\epsilon ,g)n^3$. Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Ru'e, Sau and Thilikos, which may be of independent interest.