A Simple Proof of the Existence of a Planar Separator

Understand

We provide a simple proof of the existence of a planar separator by showing that it is an easy consequence of the circle packing theorem.

• We also reprove other results on separators, including: (A) There is a simple cycle separator if the planar graph is triangulated.
• Furthermore, if each face has at most $d$ edges on its boundary, then there is a cycle separator of size O(sqrt{d n}).
• (B) For a set of n balls in R^d, that are k-ply, there is a separator, in the intersection graph of the balls, of size O(k^{1/d}n^{1-1/d}).