Lesson 7

Let us connect the theorem with the optional treewidth topic from the section on trees. There we saw the following principle: if every induced subgraph of \(G\) has a balanced separator of size at most \(k\), then \(\operatorname{tw}(G)=O(k\log n)\).

Since every induced subgraph of a planar graph is planar, the planar separator theorem gives that every \(n\)-vertex planar graph satisfies \[\operatorname{tw}(G)=O(\sqrt n\log n).\]

Corollary. Maximum independent set in an \(n\)-vertex planar graph can be solved in time \[2^{O(\sqrt n\log n)}.\]