View source for Treewidth

{{Short description|Number denoting a graph's closeness to a tree}}
{{Use mdy dates|cs1-dates=ly|date=March 2025}}
{{CS1 config|mode=cs2}}
In [[graph theory]], the '''treewidth''' of an [[undirected graph]] is an [[integer]] number which specifies, informally, how far the graph is from being a [[Tree (graph theory)|tree]]. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the [[Tree (graph theory)#Forest|forests]]. An example of graphs with treewidth at most 2 are the [[series–parallel graph]]s. The maximal graphs with treewidth exactly {{mvar|k}} are called ''[[k-tree|{{math|k}}-tree]]s'', and the graphs with treewidth at most {{mvar|k}} are called ''[[partial k-tree|partial {{math|k}}-trees]]''.{{sfnp|Bodlaender|1988}} Many other well-studied graph families also have bounded treewidth.

Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a [[tree decomposition]] of the graph, in terms of the size of the largest [[clique (graph theory)|clique]] in a [[chordal completion]] of the graph, in terms of the maximum order of a [[haven (graph theory)|haven]] describing a strategy for a [[pursuit–evasion]] game on the graph, or in terms of the maximum order of a [[Bramble (graph theory)|bramble]], a collection of connected subgraphs that all touch each other.

Treewidth is commonly used as a parameter in the [[parameterized complexity]] analysis of graph [[algorithm]]s. Many algorithms that are [[NP-hard]] for general graphs, become easier when the treewidth is bounded by a constant.

The concept of treewidth was originally introduced by {{harvs|last1 = Bertelè|first1=Umberto|last2=Brioschi|first2=Francesco|year = 1972|txt}} under the name of ''dimension''. It was later rediscovered by {{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}, based on properties that it shares with a different graph parameter, the [[Hadwiger number]]. Later it was again rediscovered by {{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}} and has since been studied by many other authors.<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>

==Definition==
[[Image:Tree decomposition.svg|thumb|240px|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 [[tree decomposition]] of a graph {{math|1={{mvar|G}} = (''V'', ''E'')}} is a tree {{mvar|T}} with nodes {{math|''X''{{sub|1}}, …, ''X''{{sub|''n''}}}}, where each {{mvar|X{{sub|i}}}} is a subset of {{mvar|V}}, satisfying the following properties<ref>{{harvtxt|Diestel|2005}} section 12.3</ref> (the term ''node'' is used to refer to a vertex of {{mvar|T}} to avoid confusion with vertices of {{mvar|G}}):
# The union of all sets {{mvar|X{{sub|i}}}} equals {{mvar|V}}. That is, each graph vertex is contained in at least one tree node.
# If {{mvar|X{{sub|i}}}} and {{mvar|X{{sub|j}}}} both contain a vertex {{mvar|v}}, then all nodes {{mvar|X{{sub|k}}}} of {{mvar|T}} in the (unique) path between {{mvar|X{{sub|i}}}} and {{mvar|X{{sub|j}}}} contain {{mvar|v}} as well. Equivalently, the tree nodes containing vertex {{mvar|v}} form a connected subtree of {{mvar|T}}.
# For every edge {{math|(''v'', ''w'')}} in the graph, there is a subset {{mvar|X{{sub|i}}}} that contains both {{mvar|v}} and {{mvar|w}}. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
The ''width'' of a tree decomposition is the size of its largest set {{mvar|X{{sub|i}}}} minus one.   The '''treewidth''' {{math|tw(''G'')}} of a graph {{mvar|G}} is the minimum width among all possible tree decompositions of {{mvar|G}}. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.

Equivalently, the treewidth of {{mvar|G}} is one less than the size of the largest [[clique (graph theory)|clique]] in the [[chordal graph]] containing {{mvar|G}} with the smallest [[maximum clique|clique number]]. A chordal graph with this clique size may be obtained by adding to {{mvar|G}} an edge between every two vertices that both belong to at least one of the sets {{mvar|X{{sub|i}}}}.

Treewidth may also be characterized in terms of [[haven (graph theory)|havens]], functions describing an evasion strategy for a certain [[pursuit–evasion]] game defined on a graph. A graph {{mvar|G}} has treewidth {{mvar|k}} if and only if it has a haven of order {{math|''k'' + 1}} but of no higher order, where a haven of order {{math|''k'' + 1}} is a function {{mvar|β}} that maps each set {{mvar|X}} of at most {{mvar|k}} vertices in {{mvar|G}} into one of the connected components of {{math|{{mvar|G}} \ ''X''}} and that obeys the [[monotonicity]] property that {{math|''&beta;''(''Y'') ⊆ ''&beta;''(''X'')}} whenever {{math|''X'' ⊆ ''Y''}}.

[[File:3x3 grid graph haven.svg|thumb|A [[Bramble (graph theory)|bramble]] of order four in a 3&times;3 grid graph, the existence of which shows that the graph has treewidth at least&nbsp;3]]
A similar characterization can also be made using [[Bramble (graph theory)|brambles]], families of connected subgraphs that all touch each other (meaning either that they share a vertex or are connected by an edge).<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref> The order of a bramble is the smallest [[hitting set]] for the family of subgraphs, and the treewidth of a graph is one less than the maximum order of a bramble.

==Examples==
Every [[complete graph]] {{mvar|K{{sub|n}}}} has treewidth{{math| ''n'' – 1}}. This is most easily seen using the definition of treewidth in terms of chordal graphs: the complete graph is already chordal, and adding more edges cannot reduce the size of its largest clique.

A connected graph with at least two vertices has treewidth 1 if and only if it is a tree. A tree has treewidth one by the same reasoning as for complete graphs (namely, it is chordal, and has maximum clique size two). Conversely, if a graph has a cycle, then every [[chordal completion]] of the graph includes at least one triangle consisting of three consecutive vertices of the cycle, from which it follows that its treewidth is at least two.

==Bounded treewidth==

===Graph families with bounded treewidth===
For any fixed constant {{mvar|k}}, the graphs of treewidth at most {{mvar|k}} are called the [[partial k-tree|partial {{mvar|k}}-trees]]. Other families of graphs with bounded treewidth include the [[cactus graph]]s, [[pseudoforest]]s, [[series–parallel graph]]s, [[outerplanar graph]]s, [[Halin graph]]s, and [[Apollonian network]]s.<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref> The [[control-flow graph]]s arising in the [[compiler|compilation]] of [[structured programming|structured programs]] also have bounded treewidth, which allows certain tasks such as [[register allocation]] to be performed efficiently on them.<ref>{{harvtxt|Thorup|1998}}.</ref>

The [[planar graph]]s do not have bounded treewidth, because the {{math|''n'' × ''n''}} [[grid graph]] is a planar graph with treewidth exactly {{mvar|n}}. Therefore, if {{mvar|F}} is a [[Graph_minor#Minor-closed_graph_families|minor-closed graph family]] with bounded treewidth, it cannot include all planar graphs. Conversely, if some planar graph cannot occur as a minor for graphs in family {{mvar|F}}, then there is a constant {{mvar|k}} such that all graphs in {{mvar|F}} have treewidth at most {{mvar|k}}. That is, the following three conditions are equivalent to each other:<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
#{{mvar|F}} is a minor-closed family of bounded-treewidth graphs;
#One of the finitely many forbidden minors characterizing {{mvar|F}} is planar;
#{{mvar|F}} is a minor-closed graph family that does not include all planar graphs.

===Forbidden minors===
[[File:Partial 3-tree forbidden minors.svg|thumb|300px|The four forbidden minors for treewidth 3: {{math|''K''{{sub|5}}}} (top-left), the graph of the octahedron (bottom-left), the Wagner graph (top-right), and the graph of the pentagonal prism (bottom-right)]]

For every finite value of {{mvar|k}}, the graphs of treewidth at most {{mvar|k}} may be characterized by a finite set of [[Forbidden graph characterization|forbidden minor]]s. (That is, any graph of treewidth {{math|> ''k''}} includes one of the graphs in the set as a minor.) Each of these sets of forbidden minors includes at least one planar graph.
*For {{math|1=''k'' = 1}}, the unique forbidden minor is a 3-vertex [[cycle graph]].<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref>
*For {{math|1=''k'' = 2}}, the unique forbidden minor is the 4-vertex [[complete graph]] {{math|''K''{{sub|4}}}}.<ref name="b98"/>
*For {{math|1=''k'' = 3}}, there are four forbidden minors: {{math|''K''{{sub|5}}}}, the graph of the [[octahedron]], the [[pentagonal prism|pentagonal]] [[prism graph]], and the [[Wagner graph]]. Of these, the two [[polyhedral graph]]s are planar.<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
For larger values of {{mvar|k}}, the number of forbidden minors grows at least as quickly as the exponential of the square root of&nbsp;{{mvar|k}}.{{sfnp|Ramachandramurthi|1997}} However, known upper bounds on the size and number of forbidden minors are much higher than this lower bound.{{sfnp|Lagergren|1993}}

==Algorithms==

===Computing the treewidth===
It is NP-complete to determine whether a given graph {{mvar|G}} has treewidth at most a given variable {{mvar|k}}.{{sfnp|Arnborg|Corneil|Proskurowski|1987}}
However, when {{mvar|k}} is any fixed constant, the graphs with treewidth {{mvar|k}} can be recognized, and a width {{mvar|k}} tree decomposition constructed for them, in linear time.<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> The time dependence of this algorithm on {{mvar|k}} is exponential.

Due to the roles the treewidth plays in an enormous number of fields, different practical and theoretical algorithms computing the treewidth of a graph were developed. Depending on the application on hand, one can prefer better approximation ratio, or better  dependence in the running time from the size of the input or the treewidth.   
The table below provides an overview of some of the treewidth  algorithms. Here {{mvar|k}} is the treewidth and {{mvar|n}} is the number of vertices of an input graph  {{mvar|G}}.
Each of the algorithms outputs in time {{math|''f''(''k'') ⋅ ''g''(''n'')}} a decomposition of width given in the Approximation column. For example, the algorithm of {{harvtxt|Bodlaender|1996}} in time {{math|''2''{{sup|''O''(''k''{{sup|3}})}}⋅''n''}} either constructs a tree decomposition of the input graph {{mvar|G}} of width at most {{mvar|k}} or reports that the treewidth of {{mvar|G}} is more than {{mvar|k}}. Similarly,  the algorithm of {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}  in time {{math|2{{sup|''O''(''k'')}}⋅''n''}} either constructs a tree decomposition of the input graph  {{mvar|G}} of width at most {{math|5''k'' + 4}} or reports that the treewidth of {{mvar|G}} is more than {{mvar|k}}. {{harvtxt|Korhonen|2021}} improved this to {{math|2''k'' + 1}} in the same running time. 

{| class="wikitable"
|-
! Approximation !! {{math|''f''(''k'')}} !! {{math|''g''(''n'')}} !! reference
|-
| exact || {{math|''O''(1)}} || {{math|''O''(''n''{{sup|''k''+2}})}} || {{harvtxt|Arnborg|Corneil|Proskurowski|1987}}
|-
|  {{math|4''k'' + 3}}  || {{math|''O''(3{{sup|3''k''}})}} || {{math|''O''(''n''{{sup|2}})}} || {{harvtxt|Robertson|Seymour|1995}}
|-
| {{math|8''k'' + 7}}|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log{{sup|2}} ''n''}} || {{harvtxt|Lagergren|1996}}
|-
| {{math|5''k'' + 4}} (or {{math|7''k'' + 6}})|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log ''n''}} || {{harvtxt|Reed|1992}}
|-
|  exact || {{math|2{{sup|''O''(''k''{{sup|3}})}}}} || {{math|''O''(''n'')}} ||{{harvtxt|Bodlaender|1996}}
|-
|  <math>O \left( k \cdot \sqrt{\log k} \right)</math> || {{math|''O''(1)}}|| {{math|''n''{{sup|''O''(1)}}}} ||{{harvtxt|Feige|Hajiaghayi|Lee |2008}}
|-
|  {{math|4.5''k'' + 4}} || {{math|2{{sup|3''k''}}}} || {{math|''n''{{sup|2}}}} ||{{harvtxt|Amir |2010}}
|-
|  {{math|{{sfrac|11|3}}''k'' + 4}} || {{math|2{{sup|3.6982''k''}}}} || {{math|''n''{{sup|3}} log{{sup|4}}''n''}} ||{{harvtxt|Amir |2010}}
|-
|  exact || {{math|''O''(1)}}|| {{math|''O''(1.7347{{sup|''n''}})}} || {{harvtxt|Fomin|Todinca|Villanger|2015}}
|-
|  {{math|3''k'' + 2}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}
|-
|  {{math|5''k'' + 4}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'')}} || {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}
|-
|  {{math|''k''{{sup|2}}}}  || {{math|''O''(''k''{{sup|7}})}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Fomin|Lokshtanov|Saurabh| Pilipczuk |2018}}
|-
|  {{math|5''k'' + 4}}  || {{math|2{{sup|8.765''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Belbasi|Fürer|2021a}}
|-
|{{math|2''k'' + 1}}
|{{math|2{{sup|''O''(''k'')}}}}
|{{math|''O''(''n'')}}
|{{harvtxt|Korhonen|2021}}
|-
|  {{math|5''k'' + 4}}  || {{math|2{{sup|6.755''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Belbasi|Fürer|2021b}}
|-
|  exact  || {{math|2{{sup|''O''(''k''{{sup|2}})}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|Korhonen|Lokshtanov|2023}}
|-
|  {{math|(1+<math>\varepsilon</math>)''k''}}  || {{math|''k''{{sup|''O''(''k''/<math>\varepsilon</math>)}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|Korhonen|Lokshtanov|2023}}
|-
|}

{{unsolved|mathematics|Can the treewidth of [[planar graph]]s be computed in polynomial time?}}
It is not known whether determining the treewidth of [[planar graph]]s is NP-complete, or whether their treewidth can be computed in [[polynomial time]].{{sfnp|Kao|2008}}

In practice, an algorithm of {{harvtxt|Shoikhet|Geiger|1997}} can determine the treewidth of graphs with up to 100 vertices and treewidth up to 11, finding a chordal completion of these graphs with the optimal treewidth.

For larger graphs, one can use search-based techniques such as [[Branch and bound|branch and bound search]] to compute the treewidth. These algorithms are [[Anytime algorithm|anytime]] in that when stopped early, they will output an upper bound on the treewidth. An algorithm of this type was proposed in 2004 by Vibhav Gogate and [[Rina Dechter]]. To provide a lower bound on treewidth for the branches of this search, they construct a [[graph minor]] by repeatedly contracting an edge between a minimum degree vertex and one of its neighbors, until just one vertex remains. The maximum of the minimum degree over these constructed minors is guaranteed to be a lower bound on the treewidth of the graph.{{sfnp|Gogate|Dechter|2004}} Alex Dow and Rich Korf further improved this algorithm using [[best-first search]].{{sfnp|Dow|Korf|2007}}

===Solving other problems on graphs of small treewidth===
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'',{{sfnp|Bertelè|Brioschi|1972}} a parameter shown to be equivalent to treewidth by {{harvtxt|Bodlaender|1998}}. Later, several authors independently observed at the end of the 1980s<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref> that many algorithmic problems that are [[NP-completeness|NP-complete]] for arbitrary graphs may be solved efficiently by [[dynamic programming]] for graphs of bounded treewidth, using the tree-decompositions of these graphs.

As an example, the problem of [[graph coloring|coloring]] a graph of treewidth {{mvar|k}} may be solved by using a [[dynamic programming]] algorithm on a tree decomposition of the graph. For each set {{mvar|X{{sub|i}}}} of the tree decomposition, and each [[Partition of a set|partition]] of the vertices of  {{mvar|X{{sub|i}}}} 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. The resulting algorithm finds an optimal coloring of an {{mvar|n}}-vertex graph in time {{math|''O''(''k''<sup>''k''+''O''(1)</sup>''n'')}}, a time bound that makes this problem [[parameterized complexity|fixed-parameter tractable]].

===Courcelle's theorem===
{{main|Courcelle's theorem}}
For a large class of problems, there is a linear time algorithm to solve a problem from the class if a [[Tree decomposition|tree-decomposition]] with constant bounded treewidth is provided. Specifically, [[Courcelle's theorem]]<ref>{{harvtxt|Courcelle|1990}}; {{harvtxt|Courcelle|1992}}</ref> states that if a graph problem can be expressed in the [[logic of graphs]] using [[Monadic second-order logic|monadic second order logic]], then it can be solved in linear time on graphs with bounded treewidth. Monadic second order logic is a language to describe graph properties that uses the following constructions: 
* Logic operations, such as <math> \wedge ,\vee ,\neg ,\Rightarrow </math>
* Membership tests, such as {{math|''e'' ∈ ''E''}}, {{math|''v'' ∈ ''V''}}
* Quantifications over vertices, edges, sets of vertices, and/or sets of edges, such as {{math|∀''v'' ∈ ''V''}}, {{math|∃''e'' ∈ ''E''}}, {{math|∃''I'' ⊆ ''V''}}, {{math|∀''F'' ⊆ ''E''}}
* Adjacency tests ({{mvar|u}} is an endpoint of {{mvar|e}}), and some extensions that allow for things such as optimization.

Consider for example the [[graph coloring|3-coloring problem]] for graphs. For a graph {{math|1=''G'' = (''V'', ''E'')}}, this problem asks if it is possible to assign each vertex {{math|''v'' ∈ ''V''}} one of the 3 colors such that no two adjacent vertices are assigned the same color.
This problem can be expressed in monadic second order logic as follows: 
:<math> \exists W_1 \subseteq V : \exists W_2 \subseteq V : \exists W_3 \subseteq V : \forall v \in V : (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge </math>
:<math> \forall v \in V : \forall w \in V : (v,w) \in E \Rightarrow (\neg (v \in W_1 \wedge w \in W_1) \wedge \neg (v \in W_2 \wedge w \in W_2) \wedge \neg (v \in W_3 \wedge w \in W_3))</math>, 
where {{math|''W''{{sub|1}}}}, {{math|''W''{{sub|2}}}}, {{math|''W''{{sub|3}}}} 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.

==Related parameters==

===Pathwidth===
The [[pathwidth]] of a graph has a very similar definition to treewidth via tree decompositions, but is restricted to tree decompositions in which the underlying tree of the decomposition is a [[path graph]]. Alternatively, the pathwidth may be defined from [[interval graph]]s analogously to the definition of treewidth from chordal graphs. As a consequence, the pathwidth of a graph is always at least as large as its treewidth, but it can only be larger by a logarithmic factor.<ref name="b98"/> Another parameter, the [[graph bandwidth]], has an analogous definition from [[proper interval graph]]s, and is at least as large as the pathwidth. Other related parameters include the [[tree-depth]], a number that is bounded for a minor-closed graph family if and only if the family excludes a path, and the [[Degeneracy (graph theory)|degeneracy]], a measure of the sparsity of a graph that is at most equal to its treewidth.

===Grid minor size===
Because the treewidth of an {{math|''n'' × ''n''}} [[grid graph]] is {{mvar|n}}, the treewidth of a graph {{mvar|G}} is always greater than or equal to the size of the largest square grid [[graph minor|minor]] of {{mvar|G}}. In the other direction, the ''grid minor theorem'' by [[Neil Robertson (mathematician)|Robertson]] and [[Paul Seymour (mathematician)|Seymour]] shows that there exists an unbounded function {{mvar|f}} such that the largest square grid minor has size at least  {{math|''f''(''r'')}} where {{mvar|r}} is the treewidth.{{sfnp|Robertson|Seymour|1986}} The best bounds known on {{mvar|f}} are that {{mvar|f}} must be at least {{math|Ω(''r''<sup>''d''</sup>)}} for some fixed constant {{math|''d'' > 0}}, and at most<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}</ref>
:<math>O \left( \sqrt{ r / \log r} \right).</math>

For the {{math|Ω}} notation in the lower bound, see [[big O notation]]. Tighter bounds are known for restricted graph families, leading to efficient algorithms for many graph optimization problems on those families through the theory of [[bidimensionality]].{{sfnp|Demaine|Hajiaghayi|2008}}
[[Halin's grid theorem]] provides an analogue of the relation between treewidth and grid minor size for infinite graphs.{{sfnp|Diestel|2004}}

===Diameter and local treewidth===
A family {{mvar|F}} of graphs closed under taking subgraphs is said to have '''bounded local treewidth''', or the '''diameter-treewidth property''', if the treewidth of the graphs in the family is [[upper bound]]ed by a function of their [[Diameter (graph theory)|diameter]]. If the class is also assumed to be closed under taking [[graph minor|minors]], then {{mvar|F}} has bounded local treewidth if and only if one of the [[Forbidden graph characterization|forbidden minor]]s for {{mvar|F}} is an [[apex graph]].{{sfnp|Eppstein|2000}} The original proofs of this result showed that treewidth in an apex-minor-free graph family grows at most doubly exponentially as a function of diameter;<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004a}}.</ref> later this was reduced to singly exponential{{sfnp|Demaine|Hajiaghayi|2008}} and finally to a linear bound.{{sfnp|Demaine|Hajiaghayi|2004b}}
Bounded local treewidth is closely related to the algorithmic theory of [[bidimensionality]],<ref>{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2004}}; {{harvtxt|Demaine|Hajiaghayi|2008}}.</ref> 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.{{sfnp|Frick|Grohe|2001}}

It is also possible for a class of graphs that is not closed under minors to have bounded local treewidth. In particular this is trivially true for a class of bounded degree graphs, as bounded diameter subgraphs have bounded size. Another example is given by [[1-planar graph]]s, graphs that can be drawn in the plane with one crossing per edge, and more generally for the graphs that can be drawn on a surface of bounded genus with a bounded number of crossings per edge. As with minor-closed graph families of bounded local treewidth, this property has pointed the way to efficient approximation algorithms for these graphs.{{sfnp|Grigoriev|Bodlaender|2007}}

===Hadwiger number and ''S''-functions===
{{harvtxt|Halin|1976}} defines a class of graph parameters that he calls {{mvar|S}}-functions, which include the treewidth. These functions from graphs to integers are required to be zero on [[empty graph|graphs with no edges]], to be [[graph minor|minor-monotone]] (a function {{mvar|f}} is referred to as "minor-monotone" if, whenever {{mvar|H}} is a minor of {{mvar|G}}, one has {{math|''f''(''H'') ≤ ''f''(''G'')}}), to increase by one when a new vertex is added that is [[universal vertex|adjacent to all previous vertices]], and to take the larger value from the two subgraphs on either side of a [[clique (graph theory)|clique]] [[Vertex separator|separator]]. The set of all such functions forms a [[complete lattice]] under the operations of elementwise minimization and maximization. The top element in this lattice is the treewidth, and the bottom element is the [[Hadwiger number]], the size of the largest [[complete graph|complete]] [[graph minor|minor]] in the given graph.

==Notes==
{{reflist|20em}}

==References==
{{refbegin}}
*{{citation
 | last = Amir | first = Eyal
 | doi = 10.1007/s00453-008-9180-4
 | issue = 4
 | journal = [[Algorithmica]]
 | mr = 2581059
 | pages = 448–479
 | title = Approximation algorithms for treewidth
 | volume = 56
 | year = 2010| s2cid = 5874913
 }}.
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Corneil | first2 = D. | author2-link = Derek Corneil
 | last3 = Proskurowski | first3 = A.
 | title = Complexity of finding embeddings in a {{nowrap|<math>k</math>-tree}}
 | journal = [[SIAM Journal on Matrix Analysis and Applications]]
 | volume = 8 | issue = 2 | year = 1987 | pages = 277–284 | doi = 10.1137/0608024}}.
*{{citation
 | last1 = Arnborg | first1 = Stefan
 | last2 = Proskurowski | first2 = Andrzej
 | last3 = Corneil | first3 = Derek G. | author3-link = Derek Corneil
 | doi = 10.1016/0012-365X(90)90292-P
 | issue = 1
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1045920
 | pages = 1–19
 | title = Forbidden minors characterization of partial 3-trees
 | volume = 80
 | year = 1990| doi-access = free
 }}.
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Proskurowski | first2 = A.
 | title = Linear time algorithms for NP-hard problems restricted to partial {{nowrap|<math>k</math>-trees}}
 | journal = [[Discrete Applied Mathematics]]
 | volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0| doi-access = free }}.
*{{citation
 | last1 = Belbasi | first1 = Mahdi
 | last2 = Fürer | first2 = Martin
 | editor1-last = Uehara | editor1-first = Ryuhei
 | editor2-last = Hong | editor2-first = Seok-Hee | editor2-link = Seok-Hee Hong
 | editor3-last = Nandy | editor3-first = Subhas C.
 | arxiv = 2010.03105
 | contribution = An improvement of Reed's treewidth approximation
 | doi = 10.1007/978-3-030-68211-8_14
 | mr = 4239527
 | pages = 166–181
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = WALCOM: Algorithms and Computation – 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings
 | volume = 12635
 | year = 2021a| isbn = 978-3-030-68210-1
 | s2cid = 222177100
 }}.
*{{citation
 | last1 = Belbasi | first1 = Mahdi
 | last2 = Fürer | first2 = Martin
 | editor1-last = Du | editor1-first = Ding-Zhu
 | editor2-last = Du | editor2-first = Donglei
 | editor3-last = Wu | editor3-first = Chenchen
 | editor4-last = Xu | editor4-first = Dachuan
 | arxiv = 2111.02614
 | contribution = Finding all leftmost separators of size <math>\le k</math>
 | doi = 10.1007/978-3-030-92681-6_23
 | pages = 273–287
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings
 | volume = 13135
 | year = 2021b| isbn = 978-3-030-92680-9
 | s2cid = 242758210
 }}
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
 | last3 = Wong | first3 = A. L.
 | title = Linear-time computation of optimal subgraphs of decomposable graphs
 | journal = Journal of Algorithms
 | volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.
*{{citation
 | last1 = Bertelè | first1 = Umberto
 | last2 = Brioschi | first2 = Francesco
 | title = Nonserial Dynamic Programming
 | year = 1972
 | publisher = Academic Press
 | isbn = 978-0-12-093450-8
 | pages = 37–38
 | url = https://books.google.com/books?id=baw3LMwm-y8C&pg=PA37}}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | contribution = Dynamic programming on graphs with bounded treewidth
 | title = Proc. 15th International Colloquium on Automata, Languages and Programming
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 317 | year = 1988 | pages = 105–118
 | doi = 10.1007/3-540-19488-6_110| citeseerx = 10.1.1.18.8503| isbn = 978-3-540-19488-0 }}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | title = A linear time algorithm for finding tree-decompositions of small treewidth
 | journal = [[SIAM Journal on Computing]]
 | volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219| citeseerx = 10.1.1.19.7484}}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | title = A partial ''k''-arboretum of graphs with bounded treewidth
 | journal = Theoretical Computer Science
 | volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4 | doi-access=free}}.
*{{citation
 | last1 = Bodlaender| first1 = Hans L.
 | last2 = Drange| first2 = Pal G.  
 | last3 = Dregi| first3 = Markus S.
 | last4 = Fomin| first4 = Fedor V.
 | last5 = Lokshtanov| first5 = Daniel
 | last6 = Pilipczuk| first6 = Michal
 | title = A <math>c^k n</math> 5-approximation algorithm for treewidth
 | journal = [[SIAM Journal on Computing]]
 | volume = 45
 | issue = 2 
 | year = 2016 
 | pages = 317–378 
 | doi = 10.1137/130947374| arxiv = 1304.6321}}.
*{{citation
 | last1 = Chekuri | first1 = Chandra
 | last2 = Chuzhoy | first2 = Julia | author2-link = Julia Chuzhoy
 | arxiv=1305.6577
 | doi = 10.1145/2820609
 | issue = 5
 | journal = [[Journal of the ACM]]
 | mr = 3593966
 | pages = A40:1–65
 | title = Polynomial bounds for the grid-minor theorem
 | volume = 63
 | year = 2016| s2cid = 209860422
 }}.
*{{citation|title = The monadic second-order logic of graphs I: Recognizable sets of finite graphs|last = Courcelle|first = B.|date = 1990|journal = [[Information and Computation]]|doi = 10.1016/0890-5401(90)90043-h|volume = 85|pages = 12–75|citeseerx = 10.1.1.158.5595}}.
*{{citation|title = The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.|last = Courcelle|first = B.|date = 1992|journal = Informatique Théorique|pages = 257–286|issue = 26}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Hajiaghayi | first3 = MohammadTaghi
 | last4 = Thilikos | first4 = Dimitrios M.
 | year = 2004
 | doi = 10.1137/S0895480103433410
 | issue = 3
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2134412
 | pages = 501–511
 | title = Bidimensional parameters and local treewidth
 | volume = 18| citeseerx = 10.1.1.107.6195| s2cid = 7803025 }}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | doi = 10.1007/s00453-004-1106-1
 | issue = 3
 | journal = [[Algorithmica]]
 | mr = 2080518
 | pages = 211–215
 | title = Diameter and treewidth in minor-closed graph families, revisited
 | volume = 40
 | year = 2004a| s2cid = 390856 }}.
*{{citation
 | last1 = Demaine | first1 = Erik D.
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | contribution = Equivalence of local treewidth and linear local treewidth and its algorithmic applications
 | location = New York
 | mr = 2290974
 | pages = 840–849
 | publisher = ACM
 | title = Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 | year = 2004b}}.
*{{citation
 | last1 = Demaine| first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi| first2 = MohammadTaghi 
 | doi = 10.1007/s00493-008-2140-4
 | issue = 1
 | journal = [[Combinatorica]]
 | pages = 19–36
 | title = Linearity of grid minors in treewidth with applications through bidimensionality
 | url = http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf
 | volume = 28
 | year = 2008| s2cid = 16520181 }}.
*{{citation
 | last = Diestel | first = Reinhard
 | doi = 10.1007/BF02941538
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | mr = 2112834
 | pages = 237–242
 | title = A short proof of Halin's grid theorem
 | volume = 74
 | year = 2004| s2cid = 124603912
 }}.
*{{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=978-3-540-26182-7
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
}}
*{{citation
 | last1 = Dow | first1 = P. Alex
 | last2 = Korf | first2 = Richard E.
 | contribution = Best-first search for treewidth
 | contribution-url = https://www.aaai.org/Library/AAAI/2007/aaai07-182.php
 | pages = 1146–1151
 | publisher = AAAI Press
 | title = Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada
 | year = 2007}}
*{{citation
 | last = Eppstein | first = D. | author-link = David Eppstein
 | doi = 10.1007/s004530010020
 | issue = 3–4
 | journal = [[Algorithmica]]
 | mr = 1759751
 | pages = 275–291
 | title = Diameter and treewidth in minor-closed graph families
 | volume = 27
 | year = 2000| arxiv = math/9907126| s2cid = 3172160 }}.
*{{citation
 | last1 = Feige | first1 = Uriel
 | last2 = Hajiaghayi | first2 = MohammadTaghi 
 | last3 = Lee| first3 = James R.
 | title = Improved approximation algorithms for minimum weight vertex separators
 | journal = [[SIAM Journal on Computing]]
 | volume = 38 | issue = 2 | year = 2008 | pages = 629–657 | doi = 10.1137/05064299X| citeseerx = 10.1.1.597.5634}}.
*{{citation
 | last1 = Fomin | first1 = Fedor V. | author1-link = Fedor Fomin
 | last2 = Todinca | first2 = Ioan
 | last3 = Villanger | first3 = Yngve
 | doi = 10.1137/140964801
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | pages = 54–87
 | title = Large induced subgraphs via triangulations and CMSO
 | volume = 44
 | year = 2015| arxiv = 1309.1559
 | s2cid = 15880453 }}.
*{{citation
 | last1 = Frick | first1 = Markus
 | last2 = Grohe | first2 = Martin | author2-link = Martin Grohe
 | doi = 10.1145/504794.504798
 | issue = 6
 | journal = [[Journal of the ACM]]
 | mr = 2143836
 | pages = 1184–1206
 | title = Deciding first-order properties of locally tree-decomposable structures
 | volume = 48
 | year = 2001| arxiv = cs/0004007
 | s2cid = 999472
 }}.
*{{citation
 | last1 = Fomin| first1 = Fedor V.
 | last2 = Lokshtanov| first2 = Daniel
 | last3 = Saurabh| first3 = Saket
 | last4 = Pilipczuk| first4 = Michal
 | last5 = Wrochna| first5 = Marcin
 | title = Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
 | journal = ACM Transactions on Algorithms
 | volume = 14
 | issue = 3 
 | year = 2018 
 | pages = 34:1–34:45 
 | doi = 10.1145/3186898| arxiv = 1511.01379| s2cid = 2144798
 }}.
*{{citation
 | last1 = Gogate | first1 = Vibhav
 | last2 = Dechter | first2 = Rina
 | editor1-last = Chickering | editor1-first = David Maxwell
 | editor2-last = Halpern | editor2-first = Joseph Y.
 | arxiv = 1207.4109
 | contribution = A complete anytime algorithm for treewidth
 | pages = 201–208
 | publisher = AUAI Press
 | title = UAI '04, Proceedings of the 20th Conference in Uncertainty in Artificial Intelligence, Banff, Canada, July 7-11, 2004
 | year = 2004}}
*{{citation
 | last1 = Grigoriev | first1 = Alexander
 | last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender
 | doi = 10.1007/s00453-007-0010-x
 | issue = 1
 | journal = [[Algorithmica]]
 | mr = 2344391
 | pages = 1–11
 | title = Algorithms for graphs embeddable with few crossings per edge
 | volume = 49
 | year = 2007| citeseerx = 10.1.1.65.5071| s2cid = 8174422
 }}.
*{{Citation
 | title = ''S''-functions for graphs
 | year = 1976
 | last = Halin | first = Rudolf | author-link = Rudolf Halin
 | journal = Journal of Geometry
 | pages = 171–186
 | volume = 8
 | issue = 1–2
 | doi=10.1007/BF01917434
| s2cid = 120256194
 }}.
*{{citation|title=	Encyclopedia of Algorithms|editor-first=Ming-Yang|editor-last=Kao|publisher=Springer|year=2008|isbn=9780387307701|contribution=Treewidth of graphs|page=969|url=https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA969|quote=Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.}}
*{{citation
 | last = Korhonen | first = Tuukka
 | contribution = A Single-Exponential Time 2-Approximation Algorithm for Treewidth
 | doi = 10.1109/FOCS52979.2021.00026
 | pages = 184–192
 | publisher = IEEE
 | title = Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science
 | arxiv = 2104.07463
 | year = 2021| isbn = 978-1-6654-2055-6
 | s2cid = 233240958
 }}.
*{{citation
 | last = Lagergren | first = Jens
 | contribution = An upper bound on the size of an obstruction
 | doi = 10.1090/conm/147/01202
 | location = Providence, RI
 | mr = 1224734
 | pages = 601–621
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Graph structure theory (Seattle, WA, 1991)
 | volume = 147
 | year = 1993| isbn = 9780821851609
 }}.
*{{citation
 | last = Lagergren | first = Jens
 | doi = 10.1006/jagm.1996.0002
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 1368716
 | pages = 20–44
 | title = Efficient parallel algorithms for graphs of bounded tree-width
 | volume = 20
 | year = 1996}}.
*{{citation
 | last = Ramachandramurthi | first = Siddharthan
 | doi = 10.1137/S0895480195280010
 | issue = 1
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1430552
 | pages = 146–157
 | title = The structure and number of obstructions to treewidth
 | volume = 10
 | year = 1997}}.
*{{citation
 | last = Reed | first = Bruce A. | author-link = Bruce Reed (mathematician)
 | editor1-last = Kosaraju | editor1-first = S. Rao
 | editor2-last = Fellows | editor2-first = Mike
 | editor3-last = Wigderson | editor3-first = Avi
 | editor4-last = Ellis | editor4-first = John A.
 | contribution = Finding approximate separators and computing tree width quickly
 | doi = 10.1145/129712.129734
 | pages = 221–228
 | publisher = ACM
 | title = Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada
 | year = 1992| s2cid = 16259988 | doi-access = free
 | isbn = 0-89791-511-9 }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph minors III: Planar tree-width
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 36
 | issue = 1 | year = 1984 | pages = 49–64
 | doi = 10.1016/0095-8956(84)90013-3| doi-access = free}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph minors V: Excluding a planar graph
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 41 | issue = 1 | year = 1986 | pages = 92–114 | doi = 10.1016/0095-8956(86)90030-4| doi-access = free }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph Minors XIII: The Disjoint Paths Problem
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 63 | issue = 1 | year = 1995 | pages = 65–110 | doi = 10.1006/jctb.1995.1006| doi-access = free }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.1006/jctb.1994.1073
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1305057
 | pages = 323–348
 | title = Quickly excluding a planar graph
 | volume = 62
 | year = 1994| doi-access = free
 }}.
*{{citation
 | last1 = Satyanarayana | first1 = A.
 | last2 = Tung | first2 = L.
 | doi = 10.1002/net.3230200304
 | issue = 3
 | journal = Networks
 | mr = 1050503
 | pages = 299–322
 | title = A characterization of partial 3-trees
 | volume = 20
 | year = 1990}}.
*{{citation
 | last1 = Seymour | first1 = Paul D. | author-link1 = Paul Seymour (mathematician)
 | last2 = Thomas | first2 = Robin | author2-link=Robin Thomas (mathematician)
 | title = Graph searching and a min-max theorem for tree-width
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 58 | issue = 1 | pages = 22–33 | doi = 10.1006/jctb.1993.1027
 | year = 1993| doi-access = free }}.
*{{citation
 | last1 = Shoikhet | first1 = Kirill
 | last2 = Geiger | first2 = Dan
 | editor1-last = Kuipers | editor1-first = Benjamin
 | editor2-last = Webber | editor2-first = Bonnie L.
 | contribution = A Practical Algorithm for Finding Optimal Triangulations
 | contribution-url = https://www.aaai.org/Library/AAAI/1997/aaai97-029.php
 | pages = 185–190
 | publisher = AAAI Press / The MIT Press
 | title = Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Providence, Rhode Island, USA
 | year = 1997}}.
*{{citation
 | last = Thorup | first = Mikkel | author-link = Mikkel Thorup
 | title = All structured programs have small tree width and good register allocation
 | journal = [[Information and Computation]]
 | volume = 142 | issue = 2 | year = 1998 | pages = 159–181 | doi = 10.1006/inco.1997.2697| doi-access = free }}.
*{{citation
 | last1 = Korhonen | first1 = Tuukka
 | last2 = Lokshtanov | first2 = Daniel
 | editor1-last = Saha | editor1-first = Barna
 | editor2-last = Servedio | editor2-first = Rocco A.
 | arxiv = 2211.07154
 | contribution = An improved parameterized algorithm for treewidth
 | doi = 10.1145/3564246.3585245
 | pages = 528–541
 | publisher = Association for Computing Machinery
 | title = Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20–23, 2023
 | year = 2023}}
{{refend}}

[[Category:Graph invariants]]
[[Category:Graph minor theory]]
[[Category:NP-complete problems]]