TOPICS

# Treewidth

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

 (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).

Special cases include

 (2) (3) (4) (5) (6) (7) (8)

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.

Graph Bandwidth, Halin Graph, Pathwidth, Tree, Tree Decomposition

## Explore with Wolfram|Alpha

More things to try:

## 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.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.

Treewidth

## Cite this as:

Weisstein, Eric W. "Treewidth." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Treewidth.html