Lesson 6

We now prove the planar separator theorem.

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

Proof. If \(G\) is disconnected and every component already has at most \(n/2\) vertices, then the empty set is a balanced separator. Otherwise, apply the argument below to the unique component with more than \(n/2\) vertices. Hence we may assume that \(G\) is connected.

Choose a vertex \(r\) and let \[L_{t}=\{v\in V(G)\colon \operatorname{dist}(r,v)=t\}\] be the BFS layers. Put \(B_{t}=L_{0}\cup L_{1}\cup…\cup L_{t}\) for \(t\ge 0\), and put \(B_{t}=\varnothing\) for \(t<0\). Every edge of \(G\) goes either inside one layer or between two consecutive layers.

Let \(k=\lceil\sqrt n\rceil\). Let \(m\) be the first index such that \(|B_{m}|>n/2\). We choose one layer before \(L_{m}\) and one layer after \(L_{m}\).

If \(m\ge k\), then among the \(k\) layers \[L_{m-k},L_{m-k+1},…,L_{m-1}\] one has size at most \(n/k\le \sqrt n\). Call it \(L_{i}\). If \(m<k\), set \(i=-1\) and \(L_{i}=\varnothing\). In both cases, \[|L_{i}|\le \sqrt n \qquad\text{and}\qquad |B_{i-1}|\le n/2.\]

Similarly, let \(D\) be the largest index with \(L_{D}\ne\varnothing\). If there are at least \(k\) layers after \(L_{m}\), then among \[L_{m+1},L_{m+2},…,L_{m+k}\] choose a layer of size at most \(n/k\le \sqrt n\) and call it \(L_{j}\). If there are fewer than \(k\) layers after \(L_{m}\), set \(j=D+1\) and \(L_{j}=\varnothing\). Then \[|L_{j}|\le \sqrt n \qquad\text{and}\qquad |V(G)\setminus B_{j}|<n/2.\] Also, by construction, \(j-i\le 2k+2\). The only part that may still be too large is the annulus \[A=L_{i+1}\cup L_{i+2}\cup…\cup L_{j-1}.\]

We will separate it using the following argument. Take the subgraph induced by \(B_{j-1}\). If \(i\ge 0\), contract the connected set \(B_{i}\) into one root vertex \(x\). This preserves planarity; the set \(B_{i}\) is connected because every vertex in it has a BFS-tree path to \(r\) staying inside \(B_{i}\). If \(i=-1\), do not contract anything and use \(r\) as the root.

Put weight \(1\) on each vertex of the annulus \(A\) and weight \(0\) on all other vertices. In the obtained planar graph every vertex is at distance at most \(j-i\) from the root. By the lemma, there is a set \(X\) of size at most \(3(j-i)+3\) such that every component after deleting \(X\) contains at most \(|A|/2\) annulus vertices.

Define \[S=L_{i}\cup L_{j}\cup (X\cap A).\] Then \[|S|\le |L_{i}|+|L_{j}|+|X|\le 2\sqrt n+3(j-i)+3\le 8\lceil\sqrt n\rceil+9.\] Thus \(|S|=O(\sqrt n)\).

It remains to check that \(S\) is balanced. Since BFS edges do not jump over layers, every component of \(G-S\) lies in one of the following three regions: \[B_{i-1},\qquad A,\qquad V(G)\setminus B_{j}.\] The first region has at most \(n/2\) vertices, and the third region has fewer than \(n/2\) vertices. A component lying in \(A\) is contained in a component produced by the weighted separator \(X\), so it contains at most \(|A|/2\le n/2\) vertices. Hence every component of \(G-S\) has at most \(n/2\) vertices.◼