Treewidth

The concept of treewidth was originally introduced by Umberto Bertelè and Francesco Brioschi (1972) under the name of dimension.

It was later rediscovered by Rudolf Halin (1976), based on properties that it shares with a different graph parameter, the Hadwiger number.

A chordal graph with this clique size may be obtained by adding to G an edge between every two vertices that both belong to at least one of the sets Xi.

Treewidth may also be characterized in terms of havens, functions describing an evasion strategy for a certain pursuit–evasion game defined on a graph.

A tree has treewidth one by the same reasoning as for complete graphs (namely, it is chordal, and has maximum clique size two).

[5] The control-flow graphs arising in the compilation of structured programs also have bounded treewidth, which allows certain tasks such as register allocation to be performed efficiently on them.

Here k is the treewidth and n is the number of vertices of an input graph G. Each of the algorithms outputs in time f(k) ⋅ g(n) a decomposition of width given in the Approximation column.

The maximum of the minimum degree over these constructed minors is guaranteed to be a lower bound on the treewidth of the graph.

At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non serial dynamic programming as long as the graph had a bounded dimension,[17] a parameter shown to be equivalent to treewidth by Bodlaender (1998).

For each set Xi of the tree decomposition, and each partition of the vertices of Xi into color classes, the algorithm determines whether that coloring is valid and can be extended to all descendant nodes in the tree decomposition, by combining information of a similar type computed and stored at those nodes.

This problem can be expressed in monadic second order logic as follows: where W1, W2, W3 represent the subsets of vertices having each of the 3 colors.

Therefore, by Courcelle's results, the 3-coloring problem can be solved in linear time for a graph given a tree-decomposition of bounded constant treewidth.

[26] Bounded local treewidth is closely related to the algorithmic theory of bidimensionality,[27] and every graph property definable in first order logic can be decided for an apex-minor-free graph family in an amount of time that is only slightly superlinear.

[29] Halin (1976) defines a class of graph parameters that he calls S-functions, which include the treewidth.

These functions from graphs to integers are required to be zero on graphs with no edges, to be minor-monotone (a function f is referred to as "minor-monotone" if, whenever H is a minor of G, one has f(H) ≤ f(G)), to increase by one when a new vertex is added that is adjacent to all previous vertices, and to take the larger value from the two subgraphs on either side of a clique separator.

The set of all such functions forms a complete lattice under the operations of elementwise minimization and maximization.

A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the tree. Each tree node lists at most three vertices, so the width of this decomposition is two.
A bramble of order four in a 3×3 grid graph, the existence of which shows that the graph has treewidth at least 3
The four forbidden minors for treewidth 3: K 5 (top-left), the graph of the octahedron (bottom-left), the Wagner graph (top-right), and the graph of the pentagonal prism (bottom-right)