Structured recursive separator decompositions for planar graphs in linear time

DOI10.1145/2488608.2488672zbMath1293.05066arXiv1208.2223OpenAlexW2166242192WikidataQ60143018 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 graphsgraph decompositioncycle separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Better distance labeling for unweighted planar graphs, Optimal decremental connectivity in planar graphs, Unnamed Item, Faster shortest paths in dense distance graphs, with applications, Approximating the k-Level in Three-Dimensional Plane Arrangements, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Unnamed Item, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Better distance labeling for unweighted planar graphs, Efficient vertex-label distance oracles for planar graphs, Shortest-path queries in static networks, Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs, Unnamed Item, Min-Cost Flow in Unit-Capacity Planar Graphs, Single-source shortest paths and strong connectivity in dynamic planar graphs, Contracting a Planar Graph Efficiently, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs, Short and Simple Cycle Separators in Planar Graphs