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 formed from a family of intervals

by creating one vertex for each interval , and connecting two vertices and by an edge whenever the corresponding two sets have a nonempty intersection. That is, the edge set of is

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.

• A graph is an interval graph if and only if it does not contain the cycle graph 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

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 is based on their complex PQ tree data structure, but 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 .

Related families of graphs

By the characterization of interval graphs as AT-free chordal graphs, interval graphs are strongly chordal graphs and hence perfect graphs. Their complements belong to the class of comparability graphs, and the comparability relations are precisely the interval orders.

From the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph, it follows that a graph and its complement are both interval graphs if and only if the graph is both a split graph and a permutation graph.

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

A graph has boxicity.

The intersection graphs of arcss 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 connected triangle-free interval graphs are exactly the caterpillar trees.

Proper interval 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. A unit interval representation without repeated intervals is necessarily a proper interval representation. Not every proper interval representation is a unit interval representation, but every proper interval graph is a unit interval graph, and vice versa. Every proper interval graph is a claw-free graph; conversely, the proper interval graphs are exactly the claw-free interval graphs. However, there exist claw-free graphs that are not interval graphs.

others. This notion extends the idea of proper interval graphs such that a 0-proper interval graph is a proper interval graph. others. This notion extends the idea of proper interval graphs such that a 0-improper interval graph is a proper interval graph. of intervals nested in each other. This is a generalization of proper interval graphs as 1-nested interval graphs are exactly proper interval graphs.

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. Cohen applied interval graphs to mathematical models of population biology, specifically food webs.

Interval graphs are used to represent resource allocation problems in operations research and scheduling theory. In these applications, each interval represents a request for a resource (such as a processing unit of a distributed computing system or a room for a class) 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. See interval scheduling for more information.

An optimal graph coloring of the interval graph represents an assignment of resources that covers all of the requests with as few resources as possible; it can be found in polynomial time by a greedy coloring algorithm that colors the intervals in sorted order by their left endpoints.

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. Interval graphs also play an important role in temporal reasoning.

Interval completions and pathwidth

is an arbitrary graph, an interval completion as a subgraph. The parameterized version of interval completion (find an interval supergraph with additional edges) is fixed parameter tractable, and moreover, is solvable in parameterized subexponential time.

The pathwidth as a subgraph.

Combinatorial enumeration

, is:

1. 1, 1, 2, 5, 15, 56, 250, 1328, 8069, 54962, 410330, 3317302, ...

unlabeled vertices, not necessarily connected, is:

1. 1, 2, 4, 10, 27, 92, 369, 1807, 10344, 67659, 491347, 3894446, ...

These numbers exhibit faster than exponential growth. Because of this fast growth rate, the interval graphs do not have bounded twin-width.

Notes

References

External links