Report Number: CS-TR-77-627
Institution: Stanford University, Department of Computer Science
Title: A separator theorem for planar graphs
Author: Lipton, Richard J.
Author: Tarjan, Robert Endre
Date: October 1977
Abstract: Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A,B,C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than $2\sqrt{2}\sqrt{2}$ vertices. We exhibit an algorithm which finds such a partition A,B,C in O(n) time.
http://i.stanford.edu/pub/cstr/reports/cs/tr/77/627/CS-TR-77-627.pdf