Short and Simple Cycle Separators in Planar Graphs
From MaRDI portal
Publication:5266605
DOI10.1145/2957318zbMath1365.68459OpenAlexW2521012255WikidataQ60143010 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
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators, Balanced line separators of unit disk graphs, Unnamed Item
Uses Software
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
