 TOPICS  # 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).

Comparability Graph

## Explore with Wolfram|Alpha More things to try:

## 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.

Interval Graph

## Cite this as:

Weisstein, Eric W. "Interval Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IntervalGraph.html