In this paper we discuss the relation between the set
of all minimal separators of a graph G on the one
hand and the set of all possible minimal chordal
triangulations of G on the other hand. We prove a 1-1
correspondence between maximal sets of pairwise
parallel minimal separators and minimal triangulations.
As a consequence, we get polynomial-time algorithms to
determine the minimum fill-in and the treewidth in
several graph classes. We apply the approach to the
class of d-trapezoid graphs for which we give the first
polynomial-time algorithms that determine the minimum
fill-in and the treewidth, respectively.
