Lesson 4

Theorem (planar separator theorem, Lipton and Tarjan (1979)). Every planar graph on \(n\) vertices has a balanced separator of size \(O(\sqrt n)\).

Here is a small example of what a separator may look like. The red vertices form the set \(S\). After deleting them, the vertices on the left and the vertices on the right lie in different connected components.