What is... Treewidth?

The treewidth of a graph, a positive integer defined using a tree of sets of vertices, is central to graph structure theory and the parametrized complexity of algorithms.Its many areas of application include sparse numerical linear algebra, Bayesian inference, control theory, game theory, lowdimensional topology, network science, and algebraic geometry. DefinitionsA common definition of treewidth involves treedecompositions, of which the following is a special case.A graph is outerplanar if it can be drawn with its vertices on the boundary of a disk and its edges as noncrossing curves in the disk.Adding artificial edges, we can augment this drawing to a triangulation, a subdivision of the disk into triangles (Fig. 1), with the following properties: