Treewidth and minimum fill-in:: Grouping the minimal separators

We use the notion of potential maximal clique to characterize the maximal cliques appearing in minimal triangulations of a graph. We show that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We prove that for all classes of graphs for which polynomial algorithms computing the treewidth and the minimum fill-in exist, we can list their potential maximal cliques in polynomial time. Our approach uni es these algorithms. Finally we show how to compute in polynomial time the potential maximal cliques of weakly triangulated graphs for which the treewidth and the minimum fill-in problems were open.