Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Branch-decomposition
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a branch-decomposition of an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> <i>G</i> is a <a href="/facts/Hierarchical_clustering/KxXs6GPK">hierarchical clustering</a> of the edges of <i>G</i>, represented by an <a href="/facts/Unrooted_binary_tree/GM5KxPBh">unrooted binary tree</a> <i>T</i> with the edges of <i>G</i> as its leaves. Removing any edge from <i>T</i> partitions the edges of <i>G</i> 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 <i>G</i> is the minimum width of any branch-decomposition of <i>G</i>. </p><p>Branchwidth is closely related to <a href="/facts/Tree_decomposition/p31V5rM2">tree-width</a>: for all graphs, both of these numbers are within a constant factor of each other, and both quantities may be characterized by <a href="/facts/Forbidden_graph_characterization/50Kex6JU">forbidden minors</a>. And as with treewidth, many graph optimization problems may be solved efficiently for graphs of small branchwidth. However, unlike treewidth, the branchwidth of <a href="/facts/Planar_graphs/plREagr9">planar graphs</a> may be computed exactly, in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>. Branch-decompositions and branchwidth may also be generalized from graphs to <a href="/facts/Matroid/5bLcGlRF">matroids</a>. </p>