Interval graph

From Wikipedia, the free encyclopedia

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 \phi.$

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.

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

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.

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.

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.