# zbMATH — the first resource for mathematics

Treewidth and pathwidth of permutation graphs. (English) Zbl 0840.05087
This paper is the first one in a series of articles using scanlines in intersection models of graphs. The new concept enables to prove that every minimal triangulation of a permutation graph into a chordal graph is an interval graph, a result that generalizes to minimal triangulations of asteroidal-triple free graphs [Discrete Appl. Math. 64, 281-287 (1995)]. Moreover, an algorithm is established that computes the treewidth (pathwidth) $$\text{tw}(G)$$ of a permutation graph $$G$$ in time $$O(|V(G)|\cdot \text{tw}(G))$$. Again, the same method applied to $$d$$-trapezoid graphs leads to algorithms computing the treewidth and pathwidth in time $$O(|V(G)|\cdot (\text{tw}(G))^{d- 1})$$ and computing the minimum fill-in and interval completion number in time $$O(|V(G)|^d)$$, if the input graph is given with model.
Reviewer: H.Müller (Jena)

##### MSC:
 05C85 Graph algorithms (graph-theoretic aspects) 68W10 Parallel algorithms in computer science 68R10 Graph theory (including graph drawing) in computer science 05C75 Structural characterization of families of graphs
Full Text: