Planar Separators
From MaRDI portal
Publication:4296512
DOI10.1137/S0895480191198768zbMath0797.05039OpenAlexW2913492813MaRDI QIDQ4296512
Noga Alon, Robin Thomas, P. D. Seymour
Publication date: 10 October 1994
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480191198768
Related Items
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Surface triangulations with isometric boundary ⋮ Unnamed Item ⋮ The game of overprescribed Cops and Robbers played on graphs ⋮ Approximation algorithms for cutting a convex polyhedron out of a sphere ⋮ On the separation profile of infinite graphs ⋮ A crossing lemma for multigraphs ⋮ On graph thickness, geometric thickness, and separator theorems ⋮ Counting cycles on planar graphs in subexponential time ⋮ Counting cycles on planar graphs in subexponential time ⋮ Treetopes and their graphs ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Theory and application of width bounded geometric separators ⋮ Spanners for geodesic graphs and visibility graphs ⋮ Vulnerability of nearest neighbor graphs ⋮ Anticoloring of a family of grid graphs ⋮ Anticoloring and separation of graphs ⋮ Planar graph bipartization in linear time ⋮ Cubic polyhedral Ramanujan graphs with face size no larger than six ⋮ A PTAS for a disc covering problem using width-bounded separators ⋮ MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Bidimensionality and Kernels ⋮ Edge integrity of nearest neighbor graphs and separator theorems ⋮ Nested cycles in large triangulations and crossing-critical graphs ⋮ Generating irregular partitionable data structures ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ Unnamed Item ⋮ A crossing lemma for multigraphs