Cutwidth II: Algorithms for partial w-trees of bounded degree

The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a vertex ordering [v1,…,vn] in a way that, for every i=1,…,n−1, there are at most k edges with one endpoint in {v1,…,vi} and the other in {vi+1,…,vn}. We examine the problem of computing in polynomial time the cutwidth of a partial w-tree with bounded degree. In particular, we show how to construct an algorithm that, in nO(w2d) steps, computes the cutwidth of any partial w-tree with vertices of degree bounded by a fixed constant d. Our algorithm is constructive in the sense that it can be adapted to output a corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree with the same time complexity.