# Interval graph

Seven intervals on the real line and the corresponding seven-vertex interval graph.

In graph theory, an interval graph is the intersection graph of a multiset 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.

## Definition

Let {I1I2, ..., In} ⊂ P(R) be a set of intervals.

The corresponding interval graph is G = (VE), where

• V = {I1I2, ..., In}, and
• {IαIβ} ∈ E if and only if Iα ∩ Iβ ≠ ∅.

From this construction one can verify a common property held by all interval graphs. That is, graph G is an interval graph if and only if the maximal cliques of G can be ordered M1M2, ..., Mk such that for any v ∈ Mi ∩ Mk, where i < k, it is also the case that v ∈ Mj for any Mj, i ≤ j ≤ k.[1]

↑Jump back a section

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

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.[1][2]

↑Jump back a section

## Related families of graphs

Interval graphs are chordal graphs and hence perfect graphs.[1][2] Their complements belong to the class of comparability graphs,[3] and the comparability relations are precisely the interval orders.[1]

The interval graphs that have an interval representation in which every two intervals are either disjoint or nested are the trivially perfect graphs.

Proper interval graphs are interval graphs that have an interval representation in which no interval properly contains any other interval; unit interval graphs are the interval graphs that have an interval representation in which each interval has unit length. Every proper interval graph is a claw-free graph. However, the converse is not true. Every claw-free graph is not necessarily a proper interval graph.[4] If the collection of segments in question is a set, i.e., no repetitions of segments is allowed, then the graph is unit interval graph if and only if it is proper interval graph.[citation needed]

The intersection graphs of arcs of a circle form circular-arc graphs, a class of graphs that contains the interval graphs. The trapezoid graphs, intersections of trapezoids whose parallel sides all lie on the same two parallel lines, are also a generalization of the interval graphs.

The pathwidth of an interval graph is one less than the size of its maximum clique (or equivalently, one less than its chromatic number), and the pathwidth of any graph G is the same as the smallest pathwidth of an interval graph that contains G as a subgraph.[5]

The connected triangle-free interval graphs are exactly the caterpillar trees.[6]

↑Jump back a section

## Applications

The mathematical theory of interval graphs was developed with a view towards applications by researchers at the RAND Corporation's mathematics department, which included young researchers—such as Peter C. Fishburn and students like Alan C. Tucker and Joel E. Cohen—besides leaders—such as Delbert Fulkerson and (recurring visitor) Victor Klee.[7] Cohen applied interval graphs to mathematical models of population biology, specifically food webs.[8]

Other applications include genetics, bioinformatics, and computer science. Finding a set of intervals that represent an interval graph can also be used as a way of assembling contiguous subsequences in DNA mapping.[9] Interval graphs are used to represent resource allocation problems in operations research and scheduling theory. 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.[10] Interval graphs also play an important role in temporal reasoning.[11]

↑Jump back a section

## Notes

↑Jump back a section

## References

↑Jump back a section