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