A Graph is an interval graph if it captures the Intersection Relation for some set of Intervals on the Real Line. Formally, is an interval graph provided that one can assign to each an interval such that is nonempty precisely when .
See also Comparability Graph
References
Booth, K. S. and Lueker, G. S. ``Testing for the Consecutive Ones Property, Interval Graphs, and Graph
Planarity using PQ-Tree Algorithms.'' J. Comput. System Sci. 13, 335-379, 1976.
Fishburn, P. C. Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. New York: Wiley, 1985.
Gilmore, P. C. and Hoffman, A. J. ``A Characterization of Comparability Graphs and of Interval Graphs.''
Canad. J. Math. 16, 539-548, 1964.
Lekkerkerker, C. G. and Boland, J. C. ``Representation of a Finite Graph by a Set of Intervals on the Real Line.''
Fund. Math. 51, 45-64, 1962.