A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
Hans L. Bodlaender · SIAM Journal on Computing · 1996
In this paper, we give for constant k a linear-time algorithm that, given a graph $G = (V,E)$, determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant k.