A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth

Abstract

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 fc edges with the one endpoint in { v 1 , . . . ,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 n°(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 the corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree in n°((wd)²) steps.