Approximate tree decompositions of planar graphs in linear time

We present the first algorithm that, on n-vertex planar graphs with treewidth k, finds a tree decomposition of width O(k) in such a time. In more detail, our algorithm has a running time of O(nk2log⁡k). We show the result as a special case of a result concerning so-called weighted treewidth of weighted graphs.