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). This project extends the research completed under CCR-94-07180: the PI has shown that every connected AT-free graph contains a dominating pair (i.e., a pair (x,y) of vertices with the property that all (x,y)-paths represent dominant sets), which can be found in linear time. In spite of these encouraging first steps in the study of AT-free graphs, the structure of the AT-free graphs is not well understood. In particular, no efficient recognition algorithm is available. The research effort investigates the ATfree 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.***
