Characterizations and algorithmic applications of chordal graph embeddings (Q1372739)

An embedding of a graph into a chordal graph (a graph with no chordless cycle of length greater than three) is a triangulation. Several classes of graphs are characterized by their minimal triangulations. The main tool for obtaining these results is the definition of a separator graph for a graph \(G\) which allows a 1-1 correspondence between the minimal triangulations of \(G\) and the maximal cliques of its separator graph. It is shown e.g. that a graph is AT-free (claw-free AT-free, a cograph) iff every minimal triangulation is an interval graph (proper interval graph, trivially perfect graph). Some algorithmic consequences for graph parameters that are related to triangulation problems (e.g. the bandwidth, treewidth, pathwidth) are also derived.