TOPICS
Search

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 intersection I_v is nonempty precisely when uv in E. An interval graph on a list l can be generated using IntervalGraph[l] in the Wolfram Language package Combinatorica` .

Star graphs are interval graphs, but cycle graphs (for n>=4) are not (Skiena 1990, p. 164). Determining if a graph is an interval graph and realizing it can be done in O(n) time (Booth and Lueker 1976; Skiena 1990, p. 164).

A graph G is an interval graph iff the vertices of G can be ordered v_1, ..., v_n such that v_i adj v_k implies v_j adj k whenever i<j<k (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

Explore with Wolfram|Alpha

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

Subject classifications