Shortest Cut Graph of a Surface with Prescribed Vertex Set

DOI10.1007/978-3-642-15781-3_9zbMath1287.05154OpenAlexW2159347714MaRDI QIDQ3586387

É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

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

Related Items (6)

Minimum Cuts in Surface Graphs ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ 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

This page was built for publication: Shortest Cut Graph of a Surface with Prescribed Vertex Set