Since the invention of PQ-trees by Booth and Lueker in 1976 the recognition of interval graphs has been simplified dramatically. In [7], we presented a very simple linear-time recognition algorithm based on scanning vertices arranged in a special perfect elimination ordering. Our approach is to decompose a given interval graph into uniquely representable components whose models can be obtained by considering “strictly overlapping” pairs of intervals. This method, however, does not yield an efficient on-line algorithm since it uses the perfect elimination scheme, which is hard to maintain efficiently in an on-line fashion.
Utilizing the decomposition approach and an “abstract” interval representation we are able to design an O(m+nlog n) time on-line recognition algorithm in this paper. The O(nlog n) factor comes from the fact that we need to maintain a concatenate queue to search for certain minimal interval “cuts” in the abstract representation.