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).
The scramble number is the most powerful known lower bound on the gonality of a graph and satisfies
 |
(1) |
where 
is the vertex
connectivity, 
is the edge connectivity, 
is the scramble number,
and 
is the gonality
of 
(Harp et al. 2020, Echavarria
et al. 2021).
For a graph with treewidth 
,
 |
(2) |
(Dujmovic and Wood 2007), where 
is the book thickness.
Special cases include
where 
denotes any tree,
any Halin
graph, 
is a cycle graph, 
is a complete graph, 
is a complete
bipartite graph, and 
is an 
grid
graph.
See also
Graph Bandwidth, Halin Graph, Pathwidth, Tree, Tree Decomposition
Explore with Wolfram|Alpha
References
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 Cybernetica 11, 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.Dujmovic, V. and Wood, D. R. "Graph Treewidth and Geometric Thickness Parameters." Disc. Comput. Geom. 37, 641-670, 2007.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." Combinatoria 32, 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. B 36, 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." Networks 20, 299-322, 1990.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Treewidth." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Treewidth.html