In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning.
Definition An interval graph is an undirected graph G formed from a family of intervals
S i , i = 0 , 1 , 2 , … {\displaystyle S_{i},\quad i=0,1,2,\dots }
by creating one vertex vi for each interval Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection. That is, the edge set of G is
E ( G ) = { ( v i , v j ) ∣ S i ∩ S j ≠ ∅ } . {\displaystyle E(G)=\{(v_{i},v_{j})\mid S_{i}\cap S_{j}\neq \emptyset \}.}
It is the intersection graph of the intervals.
Characterizations Three independent vertices form an asteroidal triple (AT) in a graph if, for each two, there exists a path containing those two but no neighbor of the third. A graph is AT-free if it has no asteroidal triple. The earliest characterization of interval graphs seems to be the following:
A graph is an interval graph if and only if it is chordal and AT-free. Other characterizations:
A graph is an interval graph if and only if its maximal cliques can be ordered M 1 , M 2 , … , M k {\displaystyle M_{1},M_{2},\dots ,M_{k}} such that each vertex that belongs to two of these cliques also belongs to all cliques between them in the ordering. That is, for every v ∈ M i ∩ M k {\displaystyle v\in M_{i}\cap M_{k}} with i < k {\displaystyle i<k} , it is also the case that v ∈ M j {\displaystyle v\in M_{j}} whenever i < j < k {\displaystyle i<j<k} . A graph is an interval graph if and only if it does not contain the cycle graph C 4 {\displaystyle C_{4}} as an induced subgraph and is the complement of a comparability graph. Various other characterizations of interval graphs and variants have been described.
Efficient recognition algorithm Determining whether a given graph G = ( V , E ) {\displaystyle G=(V,E)} is an interval graph can be done in O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} time by seeking an ordering of the maximal cliques of G {\displaystyle G} that is consecutive with respect to vertex inclusion. Many of the known algorithms for this problem work in this way, although it is also possible to recognize interval graphs in linear time without using their cliques. 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 using lexicographic breadth-first search, 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. A similar approach using a 6-sweep LexBFS algorithm is described in Corneil, Olariu & Stewart (2009).
… excerpt ends here. Continue reading the full article.
