The linear structure of graphs as seen through LBFS
An Asteroidal Triple (AT) is an independent triple of vertices such
that between any pair of vertices in the triple there is a path that
avoids the neighbourhood of the third. G is Asteroidal Triple-free
(AT-free) if it has no AT. In the 1960s Lekkerkerker and Bolland
introduced AT-free graphs and showed that a graph is an interval graph
(the intersection graph of intervals of the line) iff it is chordal (there
are no induced cycles of size greater than 3) and AT-free. Recently it
has been shown that properties of AT-free graphs seem to explain the
linear structure enjoyed by many of its subfamilies (co-comparability
graphs, trapezoid graphs, permutation graphs and interval graphs).
Lexicographic Breadth First Search (LBFS), a variant of Breadth First
Search, was developed in the 1970s by Rose, Tarjan and Lueker and shown to
yield a very simple linear time chordal graph recognition algorithm.
Recently LBFS has received a great deal of study, especially for graph
classes related to AT-free or chordal graphs.
In this talk the structural properties of these various graph classes
will be examined, especially those properties that follow from the LBFS
algorithms. Open problems will also be presented.