Treewidth and Minimum Fill-in on d-Trapezoid Graphs

We show that the minimum ll-in and the minimum interval graph completion of a d-trapezoid graph can be computed in time O(n d ). We also show that the treewidth and the pathwidth of a d-trapezoid graph can be computed in time O(ntw(G) d 1 ). In both cases, d is supposed to be a xed positive integer and it is required that a suitable intersection model of the given d-trapezoid graph is part of the input. As a consequence, each of the four graph parameters can be computed in time O(n 2 ) for trapezoid graphs and thus for permutation graphs even if no intersection model is part of the input.