LexBFS-ordering in asteroidal triple-free graphs (Q4511223)

The authors derive from a result of \textit{D. G. Corneil, S. Olariu} and \textit{L. Stewart} [Linear time algorithms for dominating pairs in asteroidal triple-free graphs, SIAM J. Comput. 28, No.~4, 1284-1297 (1999; Zbl 0926.68094)] that the vertex ordering \(<\) of an AT-free graph \(G\) obtained by applying the Lexicographic Breadth-First Search (LexBFS) twice to \(G\), where the second LexBFS procedure starts in the last vertex of the first LexBFS, has the following metric property: If \(u < v < w\) and \(d(u,w) \leq 2\) then \(d(u,v) = 1\) or \(d(v,w) \leq 2\). The authors modify this ordering to provide a new and simple linear time recognition algorithm for AT-free bipartite graphs (i.e. bipartite permutation graphs). The first linear time recognition algorithm for AT-free bipartite graphs was found by \textit{J. Spinrad, A. Brandstädt} and \textit{L. Stewart} [Bipartite permutation graphs, Discrete Appl. Math. 18, 279-292 (1987; Zbl 0628.05055)]. For the entire collection see [Zbl 0933.00045].