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.
An empty graph has treewidth 0, a tree or forest has treewidth 1, and graphs with treewidth at
most 2 correspond to series-parallel graphs. Every Halin
graph has a treewidth of 3 (Bodlaender 1988).
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).
treewidth bound
forbidden minors
1
2
3
,
octahedral graph ,
prism graph ,
Wagner graph
4
unknown finite number of minors;
at least 75 known
The scramble number is the most powerful known
lower bound on the gonality of a graph and satisfies
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.Fomin F. V. and Villanger I. "Treewidth Computation
and Extremal Combinatorics." Combinatoria32, 289-308, 2012.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.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.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.