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.