treewidth
Sign in to saveAlso known as tree-width, tw(G)
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. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called -trees, and the graphs with treewidth at most are called partial -trees. Many other well-studied graph families also have bounded treewidth.
Wikidata facts
Show 1 more fact
- Stack Exchange tag
- cs.stackexchange.com/tags/treewidth
via Wikidata · CC0
~18 min read
Article
16 sectionsContents
- Definition
- Examples
- Bounded treewidth
- Graph families with bounded treewidth
- Forbidden minors
- Algorithms
- Computing the treewidth
- Solving other problems on graphs of small treewidth
- Courcelle's theorem
- Related parameters
- Pathwidth
- Grid minor size
- Diameter and local treewidth
- Hadwiger number and {{mvar|S}}-functions
- Notes
- References
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. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called -trees, and the graphs with treewidth at most are called partial -trees. 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 in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other.