Application of a Planar Separator Theorem

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(√n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.

Authors

• Richard J. Lipton
• Robert Endre Tarjan

Keywords

• Particle separators
• Costs
• Approximation algorithms
• Application software
• Computer science
• NP-complete problem
• Complexity theory
• Dynamic programming
• Circuits
• Separation Theorem
• Vertices
• Maximum Independent Set
• Planar Graphs
• N Log N
• Triangular
• Lower Bound
• Triangulation
• Undirected
• Line Segment
• Acyclic Graph
• Topological States
• Binary Tree
• Post Office
• Class Of Graphs
• Gaussian Elimination