Interval graph

From Wikipedia, the free encyclopedia

Seven intervals of the real line and the corresponding seven-vertex 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 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.

[edit] 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 \le j \le k.$

The original linear time recognition algorithm of Booth and 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).

[edit] 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.

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.

Fulkerson, D. R.; Gross, O. A. (1965). "Incidence matrices and interval graphs". Pacific Journal of Mathematics 15: 835–855.

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.

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.