Applications of a planar separator theorem
- 1 September 1977
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 9 (02725428), 162-170
- https://doi.org/10.1109/sfcs.1977.6
Abstract
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.Keywords
This publication has 15 references indexed in Scilit:
- On Time Versus SpaceJournal of the ACM, 1977
- Space bounds for a game on graphsTheory of Computing Systems, 1976
- AlternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- Space and Time Hierarchies for Classes of Control Structures and Data StructuresJournal of the ACM, 1976
- On parallelism in turing machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- Managing Storage for Extendible ArraysSIAM Journal on Computing, 1975
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973
- An observation on time-storage trade offPublished by Association for Computing Machinery (ACM) ,1973
- Tape bounds for time-bounded turing machinesJournal of Computer and System Sciences, 1972