Branch-decomposition - Carving Width

Carving Width

Carving width is a concept defined similarly to branch width, except with edges replaced by vertices and vice versa. A carving decomposition is an unrooted binary tree with each leaf representing a vertex in the original graph, and the width of a cut is the number (or total weight in a weighted graph) of edges that are incident to a vertex in both subtrees.

Branch width algorithms typically work by reducing to an equivalent carving width problem. In particular, the carving width of the medial graph of a graph is exactly twice the branch width of the original graph.