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:

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.

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 & 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

*cite journal
author = Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch
title = A unified approach to approximating resource allocation and scheduling
journal = Journal of the ACM
year = 2001
volume = 48
issue = 5
pages = 1069–1090
url = http://portal.acm.org/citation.cfm?id=335410&coll=portal&dl=ACM
doi = 10.1145/502102.502107

*cite journal
author = Booth, K. S.; Lueker, G. S.
title = Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
journal = J. Comput. System Sci.
volume = 13
pages = 335–379
year = 1976

*cite journal
author = Fulkerson, D. R.; Gross, O. A.
title = Incidence matrices and interval graphs
journal = Pacific Journal of Mathematics
volume = 15
pages = 835–855
year = 1965

*citation
last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
title = Algorithmic Graph Theory and Perfect Graphs
publisher = Academic Press
year = 1980
isbn = 0-12-289260-7.

*cite journal
author = Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent
title = Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing
journal = Theor. Comput. Sci.
volume = 234
pages = 59–84
year = 2000
url = http://www.cs.colostate.edu/~rmm/lexbfs.ps
doi = 10.1016/S0304-3975(97)00241-7

*cite journal
author = Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E.
title = An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA
journal = Bioinformatics
volume = 10
issue = 3
year = 1994
pages = 309–317
doi = 10.1093/bioinformatics/10.3.309

External links

* cite web | url=http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_234.html | title=interval graph
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]

*