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.