Lesson 5

We start with a local statement. It says that if a planar graph has small radius, then it has a small weighted separator.

Lemma. Let \(H\) be a connected planar graph with nonnegative vertex weights \(w(v)\) and total weight \[W=\sum_{v\in V(H)}w(v).\] Suppose that for some vertex \(r\) every vertex of \(H\) is at distance at most \(d\) from \(r\). Then there is a set \(X\subseteq V(H)\) such that \[|X|\le 3d+3\] and every connected component of \(H-X\) has total weight at most \(W/2\).

Proof. The cases with at most two vertices are trivial, so assume that \(H\) has at least three vertices. Add edges to \(H\) until it becomes a maximal plane graph. This can only decrease distances from \(r\), and a separator in the denser graph is also a separator in the original graph. Thus we may assume that every face is a triangle.

Let \(T\) be a BFS tree rooted at \(r\). Every path in \(T\) from the root to a vertex has at most \(d\) edges. Consider the planar dual graph \(H^{*}\), whose vertices are the faces of \(H\). Let \(T^{*}\) be the subgraph of \(H^{*}\) consisting of the dual edges corresponding exactly to the primal edges not belonging to \(T\).

We need one standard fact: \(T^{*}\) is a tree. Indeed, \(T\) has \(|V(H)|-1\) edges, so the number of primal edges not in \(T\) is \[|E(H)|-|V(H)|+1=|F(H)|-1\] by Euler's formula. Hence \(T^{*}\) has exactly \(|F(H)|-1\) edges. If \(T^{*}\) had a cycle, then the corresponding primal edges would form a nontrivial cut in \(H\). But none of these primal edges belongs to \(T\), which is impossible because a spanning tree must cross every nontrivial cut.

Now give weights to the nodes of \(T^{*}\). For every vertex \(v\) of \(H\), choose one face incident to \(v\). If there are several such faces, choose any one of them; different vertices are allowed to choose the same face. Then add \(w(v)\) to the weight of the node of \(T^{*}\) corresponding to this face. Thus \(T^{*}\) becomes a weighted tree of total weight \(W\).

Every weighted tree has a centroid: a node such that after deleting it, every remaining component has weight at most \(W/2\). To find one, start at any node and, while some component after deleting the current node has weight more than \(W/2\), move into that component.

Let \(f\) be a centroid face of \(T^{*}\). Since \(H\) is triangulated, the boundary of \(f\) is a triangle; denote its vertices by \(a,b,c\). Let \(P_{a},P_{b},P_{c}\) be the paths in \(T\) from \(r\) to \(a,b,c\), respectively, and put \[X=V(P_{a}\cup P_{b}\cup P_{c}).\] Each of the three paths contains at most \(d+1\) vertices, so \(|X|\le 3d+3\).

It remains to explain why \(X\) is a balanced weighted separator. Let \(Q=P_{a}\cup P_{b}\cup P_{c}\). We claim that all faces touching one connected component of \(H-X\) lie in one connected component of \(T^{*}-f\).

Take an edge \(e\) whose endpoints are not in \(X\). If \(e\notin T\), then its dual edge belongs to \(T^{*}\). Also, \(e\) is not an edge of the face \(f\), because all vertices of \(f\) are in \(X\). Hence the two faces adjacent to \(e\) remain connected in \(T^{*}-f\).

Now suppose that \(e\in T\setminus Q\). Removing \(e\) from \(T\) separates a subtree not containing the root. This subtree contains none of \(a,b,c\), otherwise \(e\) would lie on one of the paths \(P_{a},P_{b},P_{c}\). Therefore the face \(f\) lies completely on the root side of this cut. The primal edges crossing the cut form a cycle in the dual graph. This dual cycle contains \(e^{*}\), and all its other edges belong to \(T^{*}\). Since \(f\) is not on this dual cycle, after deleting \(e^{*}\) we get a path in \(T^{*}-f\) between the two faces adjacent to \(e\).

Thus moving inside one component of \(H-X\) never moves between different components of \(T^{*}-f\). The centroid choice of \(f\) now implies that every component of \(H-X\) has weight at most \(W/2\).◼