<p>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.</p>

<p>The treewidth of a planar graph of diameter d is &lt;= 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]</p>

<p>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 &lt;= 2sqrt(n). Since planar graphs of diameter sqrt(n) have treewidth at most 3sqrt(n) we have that G-S has treewidth &lt;= 6sqrt(n) and so G has treewidth &lt;= 7sqrt(n). Tada.</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-05T13:42:16.937Z
2014-10-05T13:42:16.937Z
daniello
<p>The Wikipedia article about the <a href="http://en.wikipedia.org/wiki/Planar_separator_theorem" rel="nofollow">Planar Separator Theorem</a> 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.</p>

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

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

CC BY-SA 3.0
2014-10-04T23:17:39.167Z
This might be helpful: http://cstheory.stackexchange.com/a/5040/1800
Hsien-Chih Chang 張顯之
<graph-theory><planar-graphs>
Planar separator theorem and tree decomposition
antarcticfox
# Planar separator theorem and tree decomposition

(Asked by: username_0 on 2014-10-04)

The Wikipedia article about the [Planar Separator Theorem](http://en.wikipedia.org/wiki/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.

**Tags:** graph-theory, planar-graphs

> **Comments:**
> **username_1**: This might be helpful: http://cstheory.stackexchange.com/a/5040/1800  

---

## 1 answers

### Answer by username_2 on 2014-10-05. Score: 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.


---

