## 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 25-49 |

Number of pages | 25 |

Journal | Journal of Algorithms |

Volume | 56 |

Issue number | 1 |

DOIs | |

State | Published - Jul 2005 |

## Keywords

- Cutwidth
- Graph layout
- Pathwidth
- Treewidth

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics