A linear-time algorithm for finding tree-decompositions of small treewidth. (English) Zbl 0864.68074

Summary: 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\).


68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
Full Text: DOI