A Separator Theorem for Planar Graphs

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√ 2 √ n vertices. We exhibit an algorithm which finds such a partition A, B, C in $O( n )$ time.