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 k is called a k-tree, while a graph with treewidth <=k are known as partial k-trees.

Graphs with treewidth <=k may be characterized by a finite set of forbidden minors, as summarized in the following table. For the case of <=4, more than 75 minimal forbidden minors of widely varying structures are known (Sanders 1993, Sanders 1995, Chlebiková 2002).

treewidth boundforbidden minors
1C_3
2K_4
3K_5, octahedral graph K_(2,2,2), prism graph P_2 square C_5, Wagner graph M_4
4unknown 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

kappa(G)<=lambda(G)<=tw(G)<=sn(G)<=gon(G),
(1)

where kappa(G) is the vertex connectivity, lambda(G) is the edge connectivity, sn(G) is the scramble number, and gon(G) is the gonality of G (Harp et al. 2020, Echavarria et al. 2021).

Special cases include

tw(K^_)=0
(2)
tw(T)=1
(3)
tw(H)<=3
(4)
tw(C_n)=2
(5)
tw(K_n)=n-1
(6)
tw(K_(m,n))=min(m,n)
(7)
tw(P_m square P_n)=min(m,n),
(8)

where T denotes any tree, H any Halin graph, C_n is a cycle graph, K_n is a complete graph, K_(m,n) is a complete bipartite graph, and P_m square P_n is an m×n 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.Fomin F. V. and Villanger I. "Treewidth Computation and Extremal Combinatorics." Combinatoria 32, 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. 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

Treewidth

Cite this as:

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

Subject classifications