Report Number: CS-TR-77-628
Institution: Stanford University, Department of Computer Science
Title: Applications of a planar separator theorem
Author: Lipton, Richard J.
Author: Tarjan, Robert Endre
Date: October 1977
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/77/628/CS-TR-77-628.pdf