Many families of graphs including interval graphs, permutation graphs, trapezoid graphs, and co-comparability graphs demonstrate a type of linear ordering on their vertex sets. It is precisely this linear order that is exploited, in one form or another, in a search for efficient algorithms for these classes of graphs. The classes mentioned are known to have wide-ranging practical applications. In addition, they are all subfamilies of the class of graphs called the asteroidal triple-free graphs (AT-free graphs, for short). In spite of some encouraging first steps, the structure of the AT-free graphs is not well understood. In particular, no efficient recognition algorithm is available. This research effort investigates the AT-free graphs using the powerful tool of graph decomposition, with the intention to reveal new structural properties of AT-free graphs that can be exploited to obtain efficient sequential and parallel algorithms. The results provide a unifying look and a common algorithmic base from which to investigate the four classes of graphs mentioned above.
