Short and Simple Cycle Separators in Planar Graphs

DOI10.1145/2957318zbMath1365.68459WikidataQ60143010 ScholiaQ60143010MaRDI QIDQ5266605

Phitchaya Mangpo Phothilimthana, Christian Sommer, Eli Fox-Epstein, Shay Mozes

Publication date: 16 June 2017

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2957318

zbMATH Keywords

performance; algorithms; design; planar graphs; cycle separator

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

05C38: Paths and cycles

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

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Balanced line separators of unit disk graphs

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar separators and parallel polygon triangulation.
• Finding small simple cycle separators for 2-connected planar graphs
• Reduced constants for simple cycle graph separation
• Planar graphs, negative weight edges, shortest paths, and near linear time
• A linear-time algorithm to find a separator in a graph excluding a minor
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• A separator theorem for graphs of bounded genus
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• On the Problem of Partitioning Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Non-Separable and Planar Graphs
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• Short and Simple Cycle Separators in Planar Graphs
• Engineering planar separator algorithms
• Improved algorithms for min cut and max flow in undirected planar graphs
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Structured recursive separator decompositions for planar graphs in linear time
• Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
• A Theorem on Planar Graphs
• Faster shortest-path algorithms for planar graphs
• Many distances in planar graphs