A Separator Theorem for Planar Graphs

1979/04/01 by Richard J. Lipton, Robert E. Tarjan · 1,357 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Optimization and Search Problems #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Vertex (graph theory) #Joins #Partition (number theory) #Planar graph #Graph #Discrete mathematics #Computer science

paper · doi:10.1137/0136016

published in SIAM Journal on Applied Mathematics 36(2), 177-189 (Society for Industrial and Applied Mathematics)

openalex publication_date 1979/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08

Abstract

Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n / 3 vertices, and C contains no more than 2√ 2 √ n vertices. We exhibit an algorithm which finds such a partition A, B, C in O( n ) time.

Citations

• Sur le problème des courbes gauches en Topologie
• Efficient Planarity Testing
• Algorithm 447: efficient algorithms for graph manipulation
• Nested Dissection of a Regular Finite Element Mesh

Cited by

• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Separators for sphere-packings and nearest neighbor graphs
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Faster Shortest-Path Algorithms for Planar Graphs
• The analysis of a nested dissection algorithm
• New upper bounds on the decomposability of planar graphs
• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
• Reduced constants for simple cycle graph separation
• Succinct Representations of Separable Graphs
• Planar separators and the Euclidean norm
• Finding small simple cycle separators for 2-connected planar graphs
• Spectral partitioning works: Planar graphs and finite element meshes
• A separator theorem for graphs of bounded genus
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Edge separators for graphs of bounded genus with applications
• Graph separators: a parameterized view
• Moments of Inertia and Graph Separators
• A Separator Theorem in Minor-Closed Classes
• Generalized Nested Dissection
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Geometric Separators for Finite-Element Meshes
• Shortest paths in directed planar graphs with negative lengths
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• Faster shortest-path algorithms for planar graphs
• A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
• Engineering planar separator algorithms
• Disk packings and planar separators
• Computing the Girth of a Planar Graph in O(n \logn) Time
• A DETERMINISTIC LINEAR TIME ALGORITHM FOR GEOMETRIC SEPARATORS AND ITS APPLICATIONS
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Circle packing theorem [wikipedia]
• Planar separator theorem [wikipedia]