Recognizing graphs without asteroidal triples

AbstractWe 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(nm+n2), O(m3/2+n2), and O(n2.82+nm). 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