@techreport{Report-187-1988,
Title = {An Incremental Linear-Time Algorithm to Recognize Interval Graphs},
Author = {Norbert Korte and Rolf H. M\"ohring},
Pages = {68-81},
Year = {1988},
Journal = {SIAM J. Computing, 1989},
Volume = {18},
Number = {187},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {The fastest known algorithm for recognizing graphs iteratively manipulates the system of all maximal cliques of the given graph in a rather complicated way in order to construct a consecutive arrangement (more precisely: a tree representation of all possible such consecutive arrangements). We present a much simpler algorithm which uses a related, but much more informative tree representation of interval graphs. This tree is constructed in an incremental fashion by adding vertices to the graph in a predefined order such that adding a vertex $u$ takes $O(|Adj(u)| +1)$ amortized time.}
}