Interval Graph
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 
. An interval graph on a list 
can be generated
using IntervalGraph[l]
in the Wolfram Language package Combinatorica`
.
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).
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.
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.
Referenced on Wolfram|Alpha:
Interval Graph
CITE THIS AS:
Weisstein, Eric W. "Interval Graph." From
MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IntervalGraph.html
Contact the MathWorld Team
125 * 216 * 343