TRIANGULATING GRAPHS WITHOUT ASTEROIDAL TRIPLES

An asteroidal triple of a graph G is a triple of mutually independent vertices such that, between any two of them, there exists a path that avoids the neighbourhood of the third. A triangulation of G is a chord al graph H on the same vertex set that contains G as a subgraph, i.e., V(G) = V(H) and E(G) subset of or equal to E(H). We show that every s ubset of or equal to-minimal triangulation of a graph G without astero idal triples is already an interval graph. This implies that the treew idth of a graph G without asteroidal triples equals its pathwidth. Ano ther consequence is that the minimum number of additional edges in a t riangulation of G (fill-in) equals the minimum number of edges needed to embed G into an interval graph (interval completion number). The pr oof is based on the interesting property that a minimal cover of all i nduced cycles of a graph G without asteroidal triples by chords does n ot introduce new asteroidal triples. These results complement recent r esults by Corneil et al. (1994) about the linear structure of graphs w ithout asteroidal triples.