  Many algorithms have been developed for NP-hard problems on graphs with small
treewidth $k$. For example, all problems that are expressable in linear
extended monadic second order can be solved in linear time on graphs of bounded
treewidth. It turns out that the bottleneck of many algorithms for NP-hard
problems is the computation of a tree decomposition of width $O(k)$. In
particular, by the bidimensional theory, there are many linear extended monadic
second order problems that can be solved on $n$-vertex planar graphs with
treewidth $k$ in a time linear in $n$ and subexponential in $k$ if a tree
decomposition of width $O(k)$ can be found in such a 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(n k^2 \log k)$. We show the
result as a special case of a result concerning so-called weighted treewidth of
weighted graphs.
