The treewidth is a measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition.
Determining the treewidth of an arbitrary graph is an NP-hard
problem. However, many NP-hard problems on graphs of bounded treewidth can be
solved in polynomial time.
The treewidth of a disconnected graph is equal
to the maximum of the treewidths of its connected components.
A maximal graph with treewidth is called a -tree, while a graph with treewidth are known as partial -trees.
Graphs with treewidth
may be characterized by a finite set of forbidden
minors, as summarized in the following table. For the case of , more than 75 minimal forbidden minors of widely varying
structures are known (Sanders 1993, Sanders 1995, Chlebiková 2002).
Arnborg, A.; Proskurowski A.; Corneil, D. "Forbidden Minors Characterization of Partial 3-Trees." Disc. Math.80, 1-19,
1990.Bodlaender, H. "Planar Graphs with Bounded Treewidth."
Technical Report RUU-CS-88-14. Utrecht, Netherlands: Department of Computer Science,
Utrecht University, 1988.Bodlaender H. L. "A Tourist Guide
Through Treewidth." Acta Cybernetica11, 1-23, 1993.Bodlaender,
H. "Treewidth of Graphs." In Encyclopedia of Algorithms (Ed. M.Y. Kao).
Boston, MA: Springer, 2014.Chlebiková, J. "The Structure
of Obstructions to Treewidth and Pathwidth." Disc. Appl. Math.120,
61-71, 2002.Echavarria, M.; Everett, M.; Huang, R.; Jacoby, L.; Morrison,
R.; Weber, B. "On the Scramble Number of Graphs." 29 Mar 2021. https://arxiv.org/abs/2103.15253.Fomin
F. V. and Villanger I. "Treewidth Computation and Extremal Combinatorics."
Combinatoria32, 289-308, 2012.Harp, M.; Jackson, E.;
Jensen, D.; and Speeter, N. "A New Lower Bound on Graph Gonality." 1 Jun
2020. https://arxiv.org/abs/2006.01020.Harvey,
D. J. and Wood, W. R. "Parameters Tied to Treewidth." J. Graph
Th.84, 364-385, 2017.Ramachandramurthi, S. "The Structure
and Number of Obstructions to Treewidth." SIAM J. Disc. Math.10,
1997.Robertson, N. and Seymour, P. D. "Graph Minors III: Planar
Tree-Width." J. Combin. Th., Ser. B36, 49-64, 1984.Sanders,
D. P. "Linear Algorithms for Graphs of Tree-Width at Most Four. Program
of Algorithms, Combinatorics, and Optimization." Ph.D. Thesis. Atlanta, GA:
Georgia Institute of Technology, June 1993.Sanders, D. P. "On
Linear Recognization of Tree-Width at Most Four." SIAM J. Disc. Math.9,
101-117, 1995.Satyanarayana, A. and Tung, L. "A Characterization
of Partial 3-Trees." Networks20, 299-322, 1990.