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
chordal graph H on the same vertex set that contains
G as a subgraph, i. e., V(G) = V(H) and `E(G)
subseteq E(H). We show that every subseteq`-minimal
triangulation of a graph G without asteroidal triples
is already an interval graph. This implies that the
treewidth of a graph G without asteroidal triples
equals its pathwidth. Another consequence is that the
minimum number of additional edges in a triangulation
of G ( fill-in) equals the minimum number of edges
needed to embed G into an interval graph ( interval
completion number). The proof is based on the
interesting property that a minimal cover of all
induced cycles of a graph G without asteroidal
triples by chords does not introduce new asteroidal
triples. These results complement recent results by
Corneil et al. about the linear structure of graphs
without asteroidal triples.
