Planar Separators

DOI10.1137/S0895480191198768zbMATH Open0797.05039OpenAlexW2913492813MaRDI QIDQ4296512FDOQ4296512

Noga Alon, Paul Seymour, Robin Thomas

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

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

zbMATH Keywords

planar graphcornerseparator\(k\)-shield

Mathematics Subject Classification ID

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

Cited In (43)

• Vertex fault-tolerant spanners for weighted points in polygonal domains
• 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
• On the separation profile of infinite graphs
• Finding small simple cycle separators for 2-connected planar graphs
• Treetopes and their graphs
• A crossing lemma for multigraphs
• A PTAS for a disc covering problem using width-bounded separators
• Planar Crossovers
• Title not available (Why is that?)
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Bidimensionality and Kernels
• A Heuristic Algorithm for Small Separators in Arbitrary Graphs
• Title not available (Why is that?)
• 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
• NP-completeness of the Planar Separator Problems
• On graph thickness, geometric thickness, and separator theorems
• I/O-Efficient Planar Separators
• Title not available (Why is that?)
• Theory and application of width bounded geometric separators
• Nested cycles in large triangulations and crossing-critical graphs
• Title not available (Why is that?)
• MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
• The game of overprescribed Cops and Robbers played on graphs
• The first order definability of graphs with separators via the Ehrenfeucht game
• Surface triangulations with isometric boundary
• On cleaving a planar graph
• Title not available (Why is that?)
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• Planar graph bipartization in linear time
• Not all planar digraphs have small cycle separators
• Title not available (Why is that?)
• A crossing lemma for multigraphs
• Anticoloring of a family of grid graphs
• PLANAR LACES
• Reduced constants for simple cycle graph separation
• Generating irregular partitionable data structures
• Spanners for geodesic graphs and visibility graphs
• Approximation algorithms for cutting a convex polyhedron out of a sphere
• Vulnerability of nearest neighbor graphs

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)