# Treewidth

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Treewidth
> Markdown URL: https://mediated.wiki/source/Treewidth.md
> Source: https://en.wikipedia.org/wiki/Treewidth
> Source revision: 1323219473
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{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](/source/graph_theory), the '''treewidth''' of an [undirected graph](/source/undirected_graph) is an [integer](/source/integer) number which specifies, informally, how far the graph is from being a [tree](/source/Tree_(graph_theory)). The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the [forests](/source/Tree_(graph_theory)). An example of graphs with treewidth at most 2 are the [series–parallel graph](/source/series%E2%80%93parallel_graph)s. The maximal graphs with treewidth exactly {{mvar|k}} are called ''[{{math|k}}-tree](/source/k-tree)s'', and the graphs with treewidth at most {{mvar|k}} are called ''[partial {{math|k}}-trees](/source/partial_k-tree)''.{{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](/source/tree_decomposition) of the graph, in terms of the size of the largest [clique](/source/clique_(graph_theory)) in a [chordal completion](/source/chordal_completion) of the graph, in terms of the maximum order of a [haven](/source/haven_(graph_theory)) describing a strategy for a [pursuit–evasion](/source/pursuit%E2%80%93evasion) game on the graph, or in terms of the maximum order of a [bramble](/source/Bramble_(graph_theory)), a collection of connected subgraphs that all touch each other.

Treewidth is commonly used as a parameter in the [parameterized complexity](/source/parameterized_complexity) analysis of graph [algorithm](/source/algorithm)s. Many algorithms that are [NP-hard](/source/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](/source/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==
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](/source/tree_decomposition) of a graph <math>G=(V,E)</math> is a tree <math>T</math> in which each node is associated with a subset of vertices called a "bag". (The term ''node'' is used to refer to a vertex of <math>T</math> to avoid confusion with vertices of <math>G</math>). The bags <math>X_1,\dots X_t</math> must satisfy the following properties:<ref>{{harvtxt|Diestel|2005}} section 12.3</ref>
# Each graph vertex is contained in at least one bag: <math>\textstyle\bigcup_i X_i=V</math>
# If bags <math>X_i</math> and <math>X_j</math> both contain a vertex <math>v</math>, then all bags <math>X_k</math> associated with nodes in the (unique) path of <math>T</math> between <math>X_i</math> and <math>X_j</math> also contain <math>v</math> as well. Equivalently, the bags containing vertex <math>v</math> are associated with a connected subtree of <math>T</math>.
# For every edge <math>(v,w)</math> in the graph, there is at least one bag <math>X_i</math> that contains both <math>v</math> and <math>w</math>. That is, vertices are adjacent in the graph only when their corresponding subtrees have a node in common. (However, two vertices may belong to a bag without being adjacent to each other.)
The ''width'' of a tree decomposition is the size of its largest bag <math>X_i</math> minus one.   The '''treewidth''' <math>\operatorname{tw}(G)</math> of a graph <math>G</math> is the minimum width among all possible tree decompositions of <math>G</math>. 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 <math>G</math> is one less than the size of the largest [clique](/source/clique_(graph_theory)) in the [chordal graph](/source/chordal_graph) containing <math>G</math> with the smallest [clique number](/source/maximum_clique). A chordal graph with this clique size may be obtained by adding to <math>G</math> an edge between every two vertices for which at least one bag contains both vertices.

Treewidth may also be characterized in terms of [havens](/source/haven_(graph_theory)), functions describing an evasion strategy for a certain [pursuit–evasion](/source/pursuit%E2%80%93evasion) game defined on a graph. A graph <math>G</math> has treewidth <math>k</math> [if and only if](/source/if_and_only_if) it has a haven of order <math>k+1</math> but of no higher order, where a haven of order <math>k+1</math> is a function <math>\beta</math> that maps each set <math>X</math> of at most <math>k</math> vertices in <math>G</math> into one of the connected components of <math>G\setminus X</math>and that obeys the [monotonicity](/source/monotonicity) property that <math>\beta(Y)\subseteq\beta(X)</math> whenever <math>X\subset Y</math>.

[[File:3x3 grid graph haven.svg|thumb|A [bramble](/source/Bramble_(graph_theory)) 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 [brambles](/source/Bramble_(graph_theory)), 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](/source/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](/source/complete_graph) <math>K_n</math> has treewidth <math>n-1</math>. 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](/source/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 <math>k</math>, the graphs of treewidth at most <math>k</math> are called the partial <math>k</math>-trees. Other families of graphs with bounded treewidth include the [cactus graph](/source/cactus_graph)s, [pseudoforest](/source/pseudoforest)s, [series–parallel graph](/source/series%E2%80%93parallel_graph)s, [outerplanar graph](/source/outerplanar_graph)s, [Halin graph](/source/Halin_graph)s, and [Apollonian network](/source/Apollonian_network)s.<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref> The [control-flow graph](/source/control-flow_graph)s arising in the [compilation](/source/compiler) of [structured programs](/source/structured_programming) also have bounded treewidth, which allows certain tasks such as [register allocation](/source/register_allocation) to be performed efficiently on them.<ref>{{harvtxt|Thorup|1998}}.</ref>

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

===Forbidden minors===
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 <math>k</math>, the graphs of treewidth at most <math>k</math> may be characterized by a finite set of [forbidden minor](/source/Forbidden_graph_characterization)s. (That is, any graph of treewidth greater than <math>k</math> 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>k=1</math>, the unique forbidden minor is a 3-vertex [cycle graph](/source/cycle_graph).<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref>
*For <math>k=2</math>, the unique forbidden minor is the 4-vertex [complete graph](/source/complete_graph) <math>K_4</math>.<ref name="b98"/>
*For <math>k=3</math>, there are four forbidden minors: <math>K_5</math>, the graph of the [octahedron](/source/octahedron), the [pentagonal](/source/pentagonal_prism) [prism graph](/source/prism_graph), and the [Wagner graph](/source/Wagner_graph). Of these, the two [polyhedral graph](/source/polyhedral_graph)s are planar.<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
For larger values of <math>k</math>, the number of forbidden minors grows at least as quickly as an exponential function of <math>\sqrt k</math>.{{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 <math>\mathsf{NP}</math>-complete to determine whether a given graph <math>G</math> has treewidth at most a given variable <math>k</math>.{{sfnp|Arnborg|Corneil|Proskurowski|1987}}
However, when <math>k</math> is any fixed constant, the graphs with treewidth <math>k</math> can be recognized, and a width <math>k</math> tree decomposition constructed for them, in linear time.<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> The time dependence of this algorithm on <math>k</math> 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](/source/Approximation_algorithm), 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 <math>k</math> is the treewidth and <math>n</math> is the number of vertices of an input graph <math>G</math>.
Each of the algorithms outputs in time <math>f(k)\cdot g(n)</math> a decomposition of width given in the Approximation column. For example, the algorithm of {{harvtxt|Bodlaender|1996}} in time <math>2^{O(k^3)}\cdot n</math> either constructs a tree decomposition of the input graph <math>G</math> of width at most <math>k</math> or reports that the treewidth of <math>G</math> is more than <math>k</math>. Similarly,  the algorithm of {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}  in time <math>2^{O(k)}\cdot n</math> either constructs a tree decomposition of the input graph <math>G</math> of width at most <math>5k+4</math> or reports that the treewidth of <math>G</math> is more than <math>k</math>. {{harvtxt|Korhonen|2021}} improved the width of the decomposition to <math>2k+1</math> in the same running time. 

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

{{unsolved|mathematics|Can the treewidth of [planar graph](/source/planar_graph)s be computed in polynomial time?}}
It is not known whether determining the treewidth of [planar graph](/source/planar_graph)s is NP-complete, or whether their treewidth can be computed in [polynomial time](/source/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 search](/source/Branch_and_bound) to compute the treewidth. These algorithms are [anytime](/source/Anytime_algorithm) 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](/source/Rina_Dechter). To provide a lower bound on treewidth for the branches of this search, they construct a [graph minor](/source/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](/source/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](/source/combinatorial_optimization) problems defined on graphs could be efficiently solved by non serial [dynamic programming](/source/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-complete](/source/NP-completeness) for arbitrary graphs may be solved efficiently by [dynamic programming](/source/dynamic_programming) for graphs of bounded treewidth, using the tree-decompositions of these graphs.

As an example, the problem of [coloring](/source/graph_coloring) a graph of treewidth <math>k</math> may be solved by using a [dynamic programming](/source/dynamic_programming) algorithm on a tree decomposition of the graph. For each bag <math>X_i</math> of the tree decomposition, and each [partition](/source/Partition_of_a_set) of the vertices of <math>X_i</math> 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 <math>n</math>-vertex graph in time <math>O(k^{k+O(1)}n)</math>, a time bound that makes this problem [fixed-parameter tractable](/source/parameterized_complexity).

===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](/source/Tree_decomposition) with constant bounded treewidth is provided. Specifically, [Courcelle's theorem](/source/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](/source/logic_of_graphs) using [monadic second order logic](/source/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\in E</math>, <math>v\in V</math>
* Quantifications over vertices, edges, sets of vertices, and/or sets of edges, such as <math>\forall v\in V</math>, <math>\exists e\in E</math>, <math>\exists I\subset V</math>, <math>\forall F\subset E</math>
* Vertex–edge incidence tests (<math>u</math> is an endpoint of <math>e</math>), and some extensions that allow for things such as optimization.

Consider for example the [3-coloring problem](/source/graph_coloring) for graphs. For a graph <math>G=(V,E)</math>, this problem asks if it is possible to assign each vertex <math>v\in V</math> one of three colors such that no two adjacent vertices are assigned the same color.
This problem can be expressed in monadic second order logic as
<math display=block>
\exists W_1 \subseteq V\ \exists W_2 \subseteq V\ \exists W_3 \subseteq V\ \left(
\begin{align}
& \forall v \in V\  (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge{} \\
& \operatorname{independent}(W_1) \wedge{} \\
& \operatorname{independent}(W_2) \wedge{} \\
& \operatorname{independent}(W_3) \\
\end{align}
\right),
</math>
where <math>W_1</math>,<math>W_2</math>, <math>W_3</math> represent the subsets of vertices having each of the three colors, and where the subexpressions <math>\operatorname{independent}(W_i)</math> are defined to mean
<math display=block>
\operatorname{independent}(W_i)\equiv
\forall e\in E\ \exist v\in V\ (\operatorname{endpoint}(v,e)\wedge \neg v\in W_i).
</math>
(It is not necessary to include in this formula the requirement that the sets <math>W_i</math> be disjoint.)
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](/source/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](/source/path_graph). Alternatively, the pathwidth may be defined from [interval graph](/source/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](/source/graph_bandwidth), has an analogous definition from [proper interval graph](/source/proper_interval_graph)s, and is at least as large as the pathwidth. Other related parameters include the [tree-depth](/source/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](/source/Degeneracy_(graph_theory)), 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\times n</math> [grid graph](/source/grid_graph) is <math>n</math>, the treewidth of a graph <math>G</math> is always greater than or equal to the size of the largest square grid [minor](/source/graph_minor) of <math>G</math>. In the other direction, the ''grid minor theorem'' by [Robertson](/source/Neil_Robertson_(mathematician)) and [Seymour](/source/Paul_Seymour_(mathematician)) shows that there exists an unbounded function <math>f</math> such that the largest square grid minor of a graph of treewidth <math>k</math> has size at least <math>f(k)</math>.{{sfnp|Robertson|Seymour|1986}} The best bounds known on<math>f</math> are that <math>f</math> must be at least <math>\Omega(k^d)</math> for some fixed constant <math>d>0</math>, and at most<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}</ref>
<math display=block>O \left( \sqrt{ r / \log r} \right).</math>

(For the <math>\Omega</math> notation in the lower bound, see [big O notation](/source/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](/source/bidimensionality).{{sfnp|Demaine|Hajiaghayi|2008}}
[Halin's grid theorem](/source/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 <math>F</math> 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](/source/upper_bound)ed by a function of their [diameter](/source/Diameter_(graph_theory)). If the class is also assumed to be closed under taking [minors](/source/graph_minor), then <math>F</math> has bounded local treewidth if and only if one of the [forbidden minor](/source/Forbidden_graph_characterization)s for <math>F</math> is an [apex graph](/source/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](/source/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](/source/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 {{mvar|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 [graphs with no edges](/source/empty_graph), to be [minor-monotone](/source/graph_minor) (a function <math>f</math> is referred to as "minor-monotone" if, whenever <math>H</math> is a minor of <math>G</math>, one has <math>f(H)\le f(G)</math>), to increase by one when a new vertex is added that is [adjacent to all previous vertices](/source/universal_vertex), and to take the larger value from the two subgraphs on either side of a [clique](/source/clique_(graph_theory)) [separator](/source/Vertex_separator). The set of all such functions forms a [complete lattice](/source/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](/source/Hadwiger_number), the size of the largest [complete](/source/complete_graph) [minor](/source/graph_minor) in the given graph.

==Notes==
{{reflist}}

==References==
{{refbegin}}
*{{citation
 | last = Amir | first = Eyal
 | doi = 10.1007/s00453-008-9180-4
 | issue = 4
 | journal = [Algorithmica](/source/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](/source/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](/source/Discrete_Mathematics_(journal))
 | 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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/Springer_Science%2BBusiness_Media)
| 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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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
 | isbn = 978-1-4503-9913-5
 }}
{{refend}}

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

---
Adapted from the Wikipedia article [Treewidth](https://en.wikipedia.org/wiki/Treewidth) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Treewidth?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.