For example, the original linear time recognition algorithm for interval graphs by Booth and Lueker [1]} in 1976 is based on their complex PQ tree data structure (also see [2]}). Habib et al. [3]} in 2000 showed how to solve the problem more simply using lexicographic breadth-first search, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph. A similar approach using a 6-sweep LexBFS algorithm is described in Corneil, Olariu and Stewart [4]} in 2010.
