Lesson 1

Planar graphs are sparse: they have only \(O(n)\) edges. But for algorithms there is an even more important property. A planar graph can be cut into two large but noticeably smaller pieces by deleting only \(O(\sqrt n)\) vertices.

A set \(S\subseteq V(G)\) is called a balanced separator if every connected component of \(G-S\) contains at most half of all vertices of \(G\).