10.1007/978-3-662-48350-3_33
Cohen Addad, Vincent
Vincent
Cohen Addad
De Mesmay, Arnaud N
Arnaud N
De Mesmay
A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
LNCS
Springer
2015
2018-12-11T11:53:27Z
2020-01-16T12:36:12Z
conference
https://research-explorer.app.ist.ac.at/record/1685
https://research-explorer.app.ist.ac.at/record/1685.json
Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ 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 ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.
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é, Sau and Thilikos, which may be of independent interest.