Approximate Tree Decompositions of Planar Graphs in Linear Time

Frank Kammer, Torsten Tholey

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…