We present the concept of treewidth, a graph property that measures its similarity to a tree and is very useful from an algorithmic perspective. The canonical definition of treewidth, is based on the concept of a tree decomposition of a graph, which is a method of partitioning the graph into subsets of vertices that are structured as a tree. For graphs that have tree decompositions with small parts, some NP-hard optimization problems can be solved efficiently.
|
