We consider the problem of recognizing AT-free graphs. Although
there is a simple O(n3) algorithm, no faster method for solving
this problem had been known. Here we give three different
algorithms which have a better time complexity for graphs which are
sparse or have a sparse complement; in particular we give algorithms
which recognize AT-free graphs in O(n m} + n2),
O( m}3/2 + n2), and O(n2.82 + n m). In addition
we give a new characterization of graphs with bounded asteroidal
number by the help of the knotting graph, a combinatorial structure
which was introduced by Gallai for considering comparability graphs.
