ON TREEWIDTH AND MINIMUM FILL-IN OF ASTEROIDAL TRIPLE-FREE GRAPHS

We present O(n(5)R + n(3)R(3)) time algorithms to compute the treewidt h, pathwidth, minimum fill-in and minimum interval graph completion of asteroidal triple-free graphs, where n is the number of vertices and R is the number of minimal separators of the input graph. This yields polynomial time algorithms for the four NP-complete graph problems on any subclass of the asteroidal triple-free graphs that has a polynomia lly bounded number of minimal separators, as e.g. cocomparability grap hs of bounded dimension and d-trapezoid graphs for any fixed d greater than or equal to 1.