TREEWIDTH AND PATHWIDTH OF PERMUTATION GRAPHS

In this paper, we show that the treewidth and pathwidth of a permutati on graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These resu lts make permutation graphs one of the few nontrivial graph classes fo r which, at the moment, treewidth is known to be computable in polynom ial time. Our algorithm, which decides whether the treewidth (pathwidt h) is at most some given integer Ic, can be implemented to run in O(nk ) 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) time, where k is the pathwidth.