On the Tree-Width of Planar Graphs

We prove that every planar graph G of tree-length ℓ has a tree-decomposition for which every bag is the union of at most 10 shortest paths of length O(ℓ). As a consequence, the tree-width of G is bounded by O(ℓ), generalizing the linear local tree-width result of planar graphs, since the tree-length of a graph does not exceed its diameter. Such a tree-decomposition can be computed in polynomial time without any prior decomposition of the input graph.