@inbook{014841380aad452c9c8d35dc1764ca22,
title = "Treewidth and pathwidth of permutation graphs",
abstract = "In this paper we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few non-trivial graph classes for which at the moment, treewidth is known to be computable in polynomial time. Our algorithm to decide whether the treewidth (pathwidth) is at most some given integer k, can be implemented to run in O(nk^2) time, when the matching diagram is given. We show that this algorithm can easily be adapted to compute the pathwidth of a permutation graph in O(nk^2) time, where k is the pathwidth.",
author = "Hans Bodlaender and Ton Kloks and Dieter Kratsch",
year = "1993",
doi = "10.1007/3-540-56939-1_66",
language = "English",
isbn = "978-3-540-56939-8",
volume = "700",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "114--125",
editor = "Andrzej Lingas and Rolf Karlsson and Svante Carlsson",
booktitle = "Automata, Languages and Programming",
}