Live briefing
Everything about Treewidth
Number denoting a graph's closeness to a tree
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 k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: TreewidthA 5-minute orientation
- Skim a recent paper: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential TimeInfluential work since 2022
- Pick up a classic book: New Frontiers in Mining Complex PatternsThe most-reprinted book on the subject
- Read the landmark paper: A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthCited 982 times
- Go sideways: Baker's techniqueA closely related topic
- Go sideways: PathwidthA closely related topic
📖 Definitions
Noun The width (maximum number of nodes or leaves at any level) of a tree.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
A partial k-arboretum of graphs with bounded treewidth
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
Diameter and Treewidth in Minor-Closed Graph Families
Combinatorial Optimization on Graphs of Bounded Treewidth
Algorithmic Meta-theorems for Restrictions of Treewidth
A $c^k n$ 5-Approximation Algorithm for Treewidth
🆕 Influential since 2022
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
Treewidth versus clique number. II. Tree-independence number
Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
Treewidth-based algorithms for the small parsimony problem on networks
Orthogonal planarity testing of bounded treewidth graphs
📚 Books worth reading
New Frontiers in Mining Complex PatternsAnnalisa Appice · 2013- 📕Topics in structural graph theoryLowell W. Beineke, Robin J. Wilson · 2012
Approximation and Online AlgorithmsThomas Erlebach · 2013
Graph-Theoretic Concepts in Computer ScienceMartin Charles Golumbic · 2012
TreewidthTon Kloks · 1994- 📕Advanced Tools and Methods for Treewidth-Based Problem SolvingM. Hecher · 2022
Treewidth, Kernels, and AlgorithmsFedor V. Fomin, Stefan Kratsch · 2020
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Baker's technique In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs…
- Pathwidth In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number…
- Branch-decomposition In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree…
- Tree decomposition In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain…
- Bidimensionality Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions…
- Graph minor In graph theory, an undirected graph H is called a minor of the undirected graph G if H can be formed from G by deleting edges and vertices and by contracting…
- Apex graph In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called…
- Tree-depth In graph theory, the tree-depth of a connected undirected graph G {\displaystyle G} is a numerical invariant of G {\displaystyle G} , the minimum height…