A graph is an interval graph if it captures the intersectionrelation for some set of intervals
on the real line (Harary and Palmer 1973, p. 264).
Formally,
is an interval graph provided that one can assign to each an interval such that is nonempty precisely when .
Star graphs are interval graphs, but cycle graphs (for )
are not (Skiena 1990, p. 164). Determining if a graph is an interval graph and
realizing it can be done in time (Booth and Lueker 1976; Skiena 1990, p. 164).
A graph
is an interval graph iff the vertices of can be ordered , ..., such that adj implies adj whenever (West 2000, p. 346).
Every induced subgraph of an interval graph is
itself an interval graph (Jacobson et al. 1991; West 2000, p. 226).
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.Harary, F. and Palmer, E. M. "A Survey of Graphical
Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava).
Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.Jacobson,
M. S.; McMorris, F. R.; and Mulder, H. M. "Tolerance Intersection
Graphs." In Proc. Kalamazoo 1988 (Ed. Y. Alavi, G. Chartrand,
O. R. Oellermann, and A. J. Schwenk). New York: Wiley, pp. 705-724,
1991.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.Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 163-164, 1990.West, D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 195-196
and 346, 2000.
is an interval graph if it captures the intersection relation for some set of intervals
on the real line (Harary and Palmer 1973, p. 264).
Formally, 
is an interval graph provided that one can assign to each 
an interval 
such that 
is nonempty precisely when 
.
)
are not (Skiena 1990, p. 164). Determining if a graph is an interval graph and
realizing it can be done in 
time (Booth and Lueker 1976; Skiena 1990, p. 164).
is an interval graph iff the vertices of 
can be ordered 
, ..., 
such that 
adj 
implies 
adj 
whenever 
(West 2000, p. 346).
