Disk packings and planar separators

1996/01/01 by Daniel A. Spielman, Shang‐Hua Teng · 43 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #Citation #Computer science #Division (mathematics) #Library science #Mathematics

paper · pdf · doi:10.1145/237218.237404

openalex publication_date 1996/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We demonstrate that the geometric separator algorithm of Miller, Teng, Thurston, and Vavasis finds a 3/4-separator of size 1.84+ for every n node planar graph. Our bound is derived from an analysis of disk packings on the sphere, 1.

Citations

• Planar separators and the Euclidean norm
• Reduced constants for simple cycle graph separation
• Geometric Separators for Finite-Element Meshes
• Convex Representations of Graphs
• A Separator Theorem for Planar Graphs
• Finding small simple cycle separators for 2-connected planar graphs
• On the Problem of Partitioning Planar Graphs
• Small sets supporting fary embeddings of planar graphs
• How to Draw a Graph
• Generalized Nested Dissection

Cited by

• A Separator Theorem in Minor-Closed Classes
• Engineering planar separator algorithms
• Planar separator theorem [wikipedia]