Interval graph

In graph theory, an interval graph is the intersection graph of a set of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.

Formally, let

\{I_{1},I_{2},\ldots ,I_{n}\}\subset {\mathcal {P}}(R)

be a set of intervals. Then the corresponding interval graph is G = (V, E) where

V=\{I_{1},I_{2},\ldots ,I_{n}\}

and

\{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \emptyset .

Interval graphs are useful in modeling resource allocation problems in operations research. Each interval represents a request for a resource for a specific period of time; the maximum weight independent set problem for the graph represents the problem of finding the best subset of requests that can be satisfied without conflicts (Bar-Noy et al 2001). Finding a set of intervals that represent an interval graph can also be used as a way of assembling contiguous subsequences in DNA mapping (Zhang et al 1994).

Interval graphs are chordal graphs and hence perfect graphs. Their complements are comparability graphs, and the comparability relations are precisely the interval orders.

Proper interval graphs are interval graphs that have an interval representation in which no interval contains any other interval; unit interval graphs are the interval graphs that have an interval representation in which each interval has unit length. A unit interval graph is necessarily a proper interval graph; every proper interval graph is a claw-free graph.

Efficient recognition algorithms

Determining whether a given graph G = (V,E) is an interval graph can be done in O(|V|+|E|) time by seeking an ordering of the maximal cliques of G that is consecutive with respect to vertex inclusion. Formally, G is an interval graph if and only if the maximal cliques of G can be ordered

M_{1},M_{2},\ldots ,M_{k}

so that whenever $v\in M_{i}\cap M_{k}$ , then $v\in M_{j}$ for each integer $j,\ i\leq j\leq k.$

The original linear time recognition algorithm of Booth & Lueker (1976) is based on their complex PQ tree data structure, but Habib et al (2000) showed how to solve the problem more simply, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph (Golumbic 1980).

References

Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch (2001). "A unified approach to approximating resource allocation and scheduling". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Booth, K. S.; Lueker, G. S. (1976). "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms". J. Comput. System Sci. 13: 335–379.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Fulkerson, D. R.; Gross, O. A. (1965). "Incidence matrices and interval graphs". Pacific Journal of Mathematics. 15: 835–855.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.

Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000). "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing". Theor. Comput. Sci. 234: 59–84. doi:10.1016/S0304-3975(97)00241-7.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E. (1994). "An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA". Bioinformatics. 10 (3): 309–317. doi:10.1093/bioinformatics/10.3.309.{{cite journal}}: CS1 maint: multiple names: authors list (link)

External links

"interval graph". Information System on Graph Class Inclusions. {{cite web}}: External link in |work= (help)

Weisstein, Eric W. "Interval graph". MathWorld.