Cutwidth

In graph theory, the cutwidth of an undirected graph is the smallest integer ${\displaystyle k}$ with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most ${\displaystyle k}$ edges. That is, if the vertices are numbered ${\displaystyle v_1,v_2,\dots v_n}$, then for every ${\displaystyle \ell =1,2,\dots n-1}$, the number of edges ${\displaystyle v_i{v}_j}$ with ${\displaystyle i\le \ell }$ and ${\displaystyle j>\ell }$ is at most ${\displaystyle k}$.^[1]

The cutwidth of a graph has also been called its folding number.^[1] Both the vertex ordering that produces the cutwidth, and the problem of computing this ordering and the cutwidth, have been called minimum cut linear arrangement.^[2]

Cutwidth is related to several other width parameters of graphs. In particular, it is always at least as large as the treewidth or pathwidth of the same graph. However, it is at most the pathwidth multiplied by ${\displaystyle O(\mathrm{\Delta })}$, or the treewidth multiplied by ${\displaystyle O(\mathrm{\Delta }\log n)}$ where ${\displaystyle \mathrm{\Delta }}$ is the maximum degree and ${\displaystyle n}$ is the number of vertices.^[3][4] If a family of graphs has bounded maximum degree, and its graphs do not contain subdivisions of complete binary trees of unbounded size, then the graphs in the family have bounded cutwidth.^[4] In subcubic graphs (graphs of maximum degree three), the cutwidth equals the pathwidth plus one.^[5]

The cutwidth is greater than or equal to the minimum bisection number of any graph. This is minimum possible number of edges from one side to another for a partition of the vertices into two subsets of equal size (or as near equal as possible). Any linear layout of a graph, achieving its optimal cutwidth, also provides a bisection with the same number of edges, obtained by partitioning the layout into its first and second halves. The cutwidth is less than or equal to the maximum degree multiplied by the graph bandwidth, the maximum number of steps separating the endpoints of any edge in a linear arrangement chosen to minimize this quantity.^[6] Unlike bandwidth, cutwidth is unchanged when edges are subdivided into paths of more than one edge. It is closely related to the "topological bandwidth", the minimum bandwidth that can be obtained by subdividing edges of a given graph. In particular, for any tree it is sandwiched between the topological bandwidth ${\displaystyle b^{*}}$ and a slightly larger number, ${\displaystyle b^{*}+{\log }_2{b}^{*}+2}$.^[1]

Another parameter, defined similarly to cutwidth in terms of numbers of edges spanning cuts in a graph, is the