The LBFS Structure and Recognition of Interval Graphs
Derek Gordon Corneil, Stephan Olariu, Lorna K. Stewart · SIAM Journal on Discrete Mathematics · 2009
A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple–free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm.