In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, an interval graph is the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

 of a multiset

Multiset

In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...

 of intervals

Interval (mathematics)

In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

 on the real line. It has one vertex

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.

Definition

Let {I₁, I₂, ..., I_n} ⊂ P(R)
be a set of intervals.

The corresponding interval graph is G = (V, E), where

• V = {I₁, I₂, ..., I_n}, 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 M₁, M₂, ..., M_k such that
for any v ∈ M_i ∩ M_k, where i < k,
it is also the case that v ∈ M_j for any M_j, i ≤ j ≤ k.

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 clique

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

s of G that is consecutive with respect to vertex inclusion.

The original linear time recognition algorithm of is based on their complex PQ tree

PQ tree

A PQ tree is a tree-based data structure that represents a family of permutations on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one of the leaf nodes, and each non-leaf node is...

 data structure, but showed how to solve the problem more simply using lexicographic breadth-first search

Lexicographic breadth-first search

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph, that is used as part of other graph algorithms such as the recognition of chordal graphs and optimal coloring of distance-hereditary graphs...

, 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

Comparability graph

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

.

Related families of graphs

Interval graphs are chordal graph

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

s and hence perfect graph

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s. Their complements

Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

 belong to the class of comparability graph

Comparability graph

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

s, and the comparability relations are precisely the interval order

Interval order

In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...

s.

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

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

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

The intersection graphs of arc

Arc

Arc may refer to:-Mathematics:*Arc , a segment of a differentiable curve*Arc , a particular type of set of points of a projective plane*Arcminute, a measure used for angles, equal to 1/60th of a degree...

s of a circle

Circle

A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....

 form circular-arc graph

Circular-arc graph

In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect....

s, a class of graphs that contains the interval graphs. The trapezoid graph

Trapezoid graph

In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses...

s, 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.

The connected triangle-free

Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...

 interval graphs are exactly the caterpillar tree

Caterpillar tree

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices of the caterpillar are within distance 1 of a central path....

s.

Applications

Interval graphs are useful in modeling resource allocation

Resource allocation

Resource allocation is used to assign the available resources in an economic way. It is part of resource management. In project management, resource allocation is the scheduling of activities and the resources required by those activities while taking into consideration both the resource...

 problems in operations research

Operations research

Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

. Each interval represents a request for a resource for a specific period of time; the maximum weight independent set problem

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

 for the graph represents the problem of finding the best subset of requests that can be satisfied without conflicts. Finding a set of intervals that represent an interval graph can also be used as a way of assembling contiguous subsequences in DNA

DNA

Deoxyribonucleic acid is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms . The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in...

mapping.