Applications of a Planar Separator Theorem
Richard J. Lipton, Robert Endre Tarjan · SIAM Journal on Computing · 1980
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.