### Abstract

The problem of determining the cutwidth of a graph is a notoriously hard problem which remains NP-complete under severe restrictions on input graphs. Until recently, nontrivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. Very recently, Heggernes et al. (SIAM J. Discrete Math., 25 (2011), pp. 1418--1437) initiated the study of cutwidth on graph classes containing graphs of unbounded treewidth and showed that a greedy algorithm computes the cutwidth of threshold graphs. We continue this line of research and present the first polynomial-time algorithm for computing the cutwidth of bipartite permutation graphs. Our algorithm runs in linear time. We stress that the cutwidth problem is NP-complete on bipartite graphs and its computational complexity is open even on small subclasses of permutation graphs, such as trivially perfect graphs.
Keywords: graph algorithms, graph layout problems, cutwidth, bipartite permutation graphs

Original language | English |
---|---|

Pages (from-to) | 1008-1021 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 26 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2012 |

Externally published | Yes |

## Fingerprint Dive into the research topics of 'Computing the cutwidth of bipartite permutation graphs in linear time'. Together they form a unique fingerprint.

## Cite this

Heggernes, P., Hof, van 't, P., Lokshtanov, D., & Nederlof, J. (2012). Computing the cutwidth of bipartite permutation graphs in linear time.

*SIAM Journal on Discrete Mathematics*,*26*(3), 1008-1021. https://doi.org/10.1137/110830514