Shortest cut graph of a surface with prescribed vertex set

DOI10.1007/978-3-642-15781-3_9MaRDI QIDQ3586387zbMATH OpenOpenAlexFDO

Authors Éric Colin de Verdière

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15781-3_9

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• Minimum cuts and shortest homologous cycles
• Minimum Cuts in Surface Graphs
• Optimally cutting a surface into a disk
• Optimally cutting a surface into a disk

Cited in

(8)

• The inverse Voronoi problem in graphs. I: Hardness
• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• Optimally cutting a surface into a disk
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Minimum Cuts in Surface Graphs
• Computing shortest closed curves on non-orientable surfaces

This page was built for publication: Shortest cut graph of a surface with prescribed vertex set

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