2015/07/07 by Vincent Cohen-Addad, Cohen-Addad, Vincent, Arnaud de Mesmay +1
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.1507.01688
openalex publication_date 2015/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.