Treewidth and Minimum Fill-in on d-Trapezoid Graphs
Hans L. Bodlaender, Ton Kloks, Dieter Kratsch, Haiko Müller · WORLD SCIENTIFIC eBooks · 2002
We show that the minimum fill-in and the minimum interval graph comple-tion of a d-trapezoid graph can be computed in time O(nd). We also show that the treewidth and the pathwidth of a d-trapezoid graph can be computed by an O(n tw(G)d1) time algorithm. For both algorithms, d is supposed to be a fixed 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, the minimum fill-in and the minimum interval graph com-pletion as well as the treewidth and the pathwidth of a given trapezoid graph (or permutation graph) can be computed in time O(n2), even if no intersection model is part of the input. 1