---
res:
bibo_abstract:
- "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.\r\nOur 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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vincent
foaf_name: Cohen Addad, Vincent
foaf_surname: Cohen Addad
- foaf_Person:
foaf_givenName: Arnaud N
foaf_name: De Mesmay, Arnaud N
foaf_surname: De Mesmay
foaf_workInfoHomepage: http://www.librecat.org/personId=3DB2F25C-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1007/978-3-662-48350-3_33
bibo_volume: 9294
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: A fixed parameter tractable approximation scheme for the optimal cut
graph of a surface@
...