Planar Separators

DOI10.1137/S0895480191198768MaRDI QIDQ4296512zbMATH OpenOpenAlexFDO

Authors Noga Alon, Robin Thomas, Paul 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

zbMATH Keywords

planar graphcornerseparator\(k\)-shield

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Recommendations

• scientific article; zbMATH DE number 867693
• \(N\)-separators in planar graphs
• scientific article; zbMATH DE number 1979709
• Finding small simple cycle separators for 2-connected planar graphs
• Weighted graph separators and their applications

Cited in

(47)

• Vulnerability of nearest neighbor graphs
• Weighted graph separators and their applications
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Edge integrity of nearest neighbor graphs and separator theorems
• Cubic polyhedral Ramanujan graphs with face size no larger than six
• Anticoloring and separation of graphs
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Finding small simple cycle separators for 2-connected planar graphs
• On the separation profile of infinite graphs
• Treetopes and their graphs
• On the path separability of planar graphs
• A crossing lemma for multigraphs
• Non-existence of annular separators in geometric graphs
• A PTAS for a disc covering problem using width-bounded separators
• \(N\)-separators in planar graphs
• Planar Crossovers
• scientific article; zbMATH DE number 4127226 (Why is no real title available?)
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• A Heuristic Algorithm for Small Separators in Arbitrary Graphs
• scientific article; zbMATH DE number 4101213 (Why is no real title available?)
• Separator theorems and Turán-type results for planar intersection graphs
• Counting cycles on planar graphs in subexponential time
• Counting cycles on planar graphs in subexponential time
• On graph thickness, geometric thickness, and separator theorems
• NP-completeness of the Planar Separator Problems
• I/O-Efficient Planar Separators
• Theory and application of width bounded geometric separators
• Nested cycles in large triangulations and crossing-critical graphs
• scientific article; zbMATH DE number 4064516 (Why is no real title available?)
• MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
• The game of overprescribed Cops and Robbers played on graphs
• Surface triangulations with isometric boundary
• The first order definability of graphs with separators via the Ehrenfeucht game
• On cleaving a planar graph
• scientific article; zbMATH DE number 1979709 (Why is no real title available?)
• Planar graph bipartization in linear time
• Not all planar digraphs have small cycle separators
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• A crossing lemma for multigraphs
• Anticoloring of a family of grid graphs
• Almost polynomial hardness of node-disjoint paths in grids
• Reduced constants for simple cycle graph separation
• PLANAR LACES
• Generating irregular partitionable data structures
• Bidimensionality and kernels
• Spanners for geodesic graphs and visibility graphs
• Approximation algorithms for cutting a convex polyhedron out of a sphere

This page was built for publication: Planar Separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4296512)