Interval Graph

A Graph $G = (V, E)$ is an interval graph if it captures the Intersection Relation for some set of Intervals on the Real Line. Formally, $P$ is an interval graph provided that one can assign to each $v \in V$ an interval $I_v$ such that $I_u \cap I_v$ is nonempty precisely when $uv \in E$.

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.