Let tw(G), pw(G), c(G), ℝ(G) denote, respectively, the tree-width, path-width, cutwidth and the maximum degree of a graph G on n vertices. It is known that c(G)≥tw(G). The authors prove that c(G)=O(tw(G)ëℝ(G)ëlogn), and if ({Xi:i∈I∈, T=(I,A)) is a tree decomposition of G with tree-width∈k then c(G)∈(k+1)ëℝ(G)ëc(T). In case that a tree decomposition is given, or that the tree-width is bounded by a constant, efficient algorithms for finding a numbering with cutwidth within the upper bounds are implicit in the proofs. The authors obtain the above results by showing that pw(G)=O(lognëtw(G)), and pw(G)∈(k+1)ëc(T).
