Structured recursive separator decompositions for planar graphs in linear time

DOI10.1145/2488608.2488672zbMath1293.05066arXiv1208.2223WikidataQ60143018 ScholiaQ60143018MaRDI QIDQ5495821

Shay Mozes, Christian Sommer, Philip N. Klein

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

planar graphs; graph decomposition; cycle separator

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C10: Planar graphs; geometric and topological aspects of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Approximating the k-Level in Three-Dimensional Plane Arrangements, Unnamed Item, Unnamed Item, Shortest-path queries in static networks, Short and Simple Cycle Separators in Planar Graphs, Optimal decremental connectivity in planar graphs, Faster shortest paths in dense distance graphs, with applications, Efficient vertex-label distance oracles for planar graphs, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths