In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, an interval graph is an
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
formed from a set of
intervals on the
real line
A number line is a graphical representation of a straight line that serves as spatial representation of numbers, usually graduated like a ruler with a particular origin (geometry), origin point representing the number zero and evenly spaced mark ...
,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of the intervals.
Interval graphs are
chordal graphs and
perfect graph
In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...
s. They can be recognized in
linear time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
, and an optimal
graph coloring
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
or
maximum clique
In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of th ...
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 interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysi ...
s.
These graphs have been used to model
food web
A food web is the natural interconnection of food chains and a graphical representation of what-eats-what in an ecological community. Position in the food web, or trophic level, is used in ecology to broadly classify organisms as autotrophs or he ...
s, and to study
scheduling
A schedule (, ) or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things ...
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
Deoxyribonucleic acid (; DNA) is a polymer composed of two polynucleotide chains that coil around each other to form a double helix. The polymer carries genetic instructions for the development, functioning, growth and reproduction of al ...
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
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
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 clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...
can be ordered
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
with