Graph invariants | Graph minor theory | Matroid theory | Trees (graph theory)
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 T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G. Branchwidth is closely related to tree-width: for all graphs, both of these numbers are within a constant factor of each other, and both quantities may be characterized by forbidden minors. And as with treewidth, many graph optimization problems may be solved efficiently for graphs of small branchwidth. However, unlike treewidth, the branchwidth of planar graphs may be computed exactly, in polynomial time. Branch-decompositions and branchwidth may also be generalized from graphs to matroids. (Wikipedia).
