Interval graph
From Free net encyclopedia
In graph theory, an interval graph is a graph that captures the intersections among a set of intervals on the real line.
Formally, let
- <math>I_1, I_2, \ldots I_n \in R</math>
be a set of intervals. Then the corresponding interval graph is G = (V, E) where
- <math>V = \{I_1, I_2, \ldots I_n\}</math>
and
- <math> (I_\alpha, I_\beta) \in E \iff I_\alpha \cap I_\beta \neq \phi. </math>
That is, the nodes of the graph are the intervals and there is an edge corresponding to each pair of intersecting intervals.
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.
Interval graphs are chordal graphs and hence perfect graphs. 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
- <math> M_1, M_2, \ldots, M_k </math>
so that whenever <math> v \in M_i \cap M_k </math>, then <math>v \in M_j</math> for each integer <math>j,\ i \le j \le k</math>
External link
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.
Fulkerson, D. R. and Gross, O. A. "Incidence matrices and interval graphs." Pacific Journal of Math. 15, 835-855, 1965.