A fixed parameter tractable approximation scheme for the optimal cut graph of a surface

DOI10.1007/978-3-662-48350-3_33MaRDI QIDQ3452802zbMATH OpenOpenAlexFDO

Authors Vincent Cohen-Addad, Arnaud de Mesmay

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.01688

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational aspects of digital topology (68U03)

Abstract: 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 parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any $varepsilon>0$, we show how to compute a $(1+varepsilon)$ approximation of the shortest cut graph in time $f(varepsilon,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.

Recommendations

• Shortest cut graph of a surface with prescribed vertex set
• Minimum Cuts in Surface Graphs
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Optimally cutting a surface into a disk

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 2080246 (Why is no real title available?)
• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• Approximation algorithms via contraction decomposition
• Combinatorial optimization of cycles and bases
• Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
• Dynamic programming for graphs on surfaces
• Graph minors. X: Obstructions to tree-decomposition
• On self duality of pathwidth in polyhedral graph embeddings
• Optimally cutting a surface into a disk
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Surface split decompositions and subgraph isomorphism in graphs on surfaces
• Tree-width of hypergraphs and surface duality

Cited in

(9)

• Shortest cut graph of a surface with prescribed vertex set
• On graph approximations of surfaces with small area
• An optimal algorithm for the minimum edge cardinality cut surface problem
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Optimally cutting a surface into a disk
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• On the biplanarity of blowups
• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• Almost tight lower bounds for hard cutting problems in embedded graphs

This page was built for publication: A fixed parameter tractable approximation scheme for the optimal cut graph of a surface

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452802)