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)

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: DOI