Applications of a Planar Separator Theorem
Authors:
- Richard J. LiptonRLRichard J. Lipton
- Robert Endre TarjanRTRobert Endre Tarjan
- 1 August 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 9 (3) , 615-627
Abstract
Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only $O(\sqrt 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.
Keywords
This publication has 22 references indexed in Scilit:
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Generalized Nested DissectionSIAM Journal on Numerical Analysis, 1979
- Triangulating a simple polygonInformation Processing Letters, 1978
- On the independence ratio of a graphJournal of Graph Theory, 1978
- Preserving average proximity in arraysCommunications of the ACM, 1978
- The monotone and planar circuit value problems are log space complete for PACM SIGACT News, 1977
- On Time Versus SpaceJournal of the ACM, 1977
- Space and Time Hierarchies for Classes of Control Structures and Data StructuresJournal of the ACM, 1976
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973