Treewidth

Treewidth is a graph parameter defined by the smallest possible maximum bag size minus one in a tree decomposition. It measures how closely a graph can be organized around a tree without losing its edges.

Tree decomposition: A tree-shaped arrangement of vertex sets in which every graph edge appears in a bag and each vertex’s bags form a connected subtree. Treewidth is the minimum width among all tree decompositions of the graph.
Pathwidth: A graph parameter defined by tree decompositions whose bags lie along a path. It uses the same bag-width measure as treewidth but imposes a more restrictive structure.
Dynamic programming on tree decompositions: An algorithmic method that solves graph problems by combining partial solutions across decomposition bags. Small bags keep the number of partial states manageable for many computations.
Branchwidth: A graph width parameter defined by edge separations arranged in a subcubic tree. It measures related decomposability, often giving bounds comparable to treewidth.
Cycle graph: A graph whose vertices form one cycle, with edges joining consecutive vertices. Every cycle with at least three vertices has treewidth two.
Tree: A connected graph with no cycles. A tree decomposition organizes overlapping vertex bags in a tree structure.
Tree-depth: A graph parameter measuring the minimum height of a rooted forest whose ancestor-descendant closure contains the graph. It measures a different kind of tree-like simplicity and can be much larger or smaller than treewidth.
Courcelle's theorem: A theorem stating that every graph property expressible in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. It gives a broad tractability result for graph properties on bounded-treewidth inputs.
Clique-width: A graph parameter measuring the number of labels needed to construct a graph using specified operations. Some graph families have bounded clique-width but unbounded treewidth, so the parameters capture different structure.
Complete graph: A graph in which every pair of distinct vertices is adjacent. A complete graph on n vertices has treewidth n minus one.

Linked from 11 pages