Many algorithms have been
developed for NP-hard problems on graphs with small treewidth
k . For example, all problems that are expressible in linear exten
ded monadic second or
der can be solved in linear time on graphs of boun
ded 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)den">de">. In particular, by the bidimensional theory, there are many linear exten
ded monadic second or
der 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)den">de"> 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)den">de"> in such a time. In more detail, our algorithm has a running time of dec08a9683bfc00cb8cbf" title="Click to view the MathML source">O(nk2logk)den">de">. We show the result as a special case of a result concerning so-called weighted treewidth of weighted graphs.