Planar separator theorem and tree decomposition

Question

The Wikipedia article about the Planar Separator Theorem states that it is possible to use a hierarchy of separators to construct a tree decomposition for a planar graph and moreover provides an $\mathcal{O}(\sqrt{n})$ upper bound for the tree width of an $n$ vertex planar graph.

I have difficulties in understanding the hierarchy and moreover in checking that the resulting binary tree is a tree decomposition.

I would really appreciate if you could help me or point to a reference that elaborates on it.

Answer 1

As far as i know the simplest (in my opinion) self contained proof of the planar separator theorem is unpublished; it is a combination of the following (somewhat non-trivial) theorem with the "Baker layering" trick.

The treewidth of a planar graph of diameter d is <= 3d-1 [H. L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1–45, 1998, Theorem 83]

Now to the "Baker layering" trick: do a BFS from an arbitrary vertex and number the layers 1,2....sqrt(n), 1, 2, ... sqrt(n) .. etc Now there exists an i such that the total number of vertices living in layers labelled i is at most sqrt(n). Let the set of these vertices be S. Consider any connected component of G-S. Such a component must live in at most sqrt(n) consecutive layers, and thus it has diameter <= 2sqrt(n). Since planar graphs of diameter sqrt(n) have treewidth at most 3sqrt(n) we have that G-S has treewidth <= 6sqrt(n) and so G has treewidth <= 7sqrt(n). Tada.

There is a small silly bug in the proof above; the fact that a connected component of G\S lives inside sqrt(n) layers does not mean that the diameter is actually at most sqrt(n) ... but thus is easily fixed by contracting the layers up until the layer of this component into a single vertex. Then diameter of (a supergraph of the component) is at most 2sqrt(n), and we are done.