HOME

TheInfoList



OR:

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 :S_i,\quad i=0,1,2,\dots 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 :E(G)=\. 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 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\in M_i\cap M_k with i, it is also the case that v\in M_j whenever i. * A graph is an interval graph if and only if it does not contain the
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
C_4 as an
induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...
and is the complement of a
comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
. Various other characterizations of interval graphs and variants have been described.


Efficient recognition algorithm

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. 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 Complement may refer to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class collections into complementary sets * Complementary color, in the visu ...
is a
comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
. 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 graph In the mathematics, mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph and every cycle (graph theory), cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two Vertex ...
s and hence
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. Their complements belong to the class of
comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
s, 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 Complement may refer to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class collections into complementary sets * Complementary color, in the visu ...
is a
comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
, it follows that graph and its complement are both interval graphs if and only if the graph is both a
split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by , where they called these ...
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 graph In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were na ...
s. A graph has
boxicity In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there mus ...
at most one if and only if it is an interval graph; the boxicity of an arbitrary graph G is the minimum number of interval graphs on the same set of vertices such that the intersection of the edges sets of the interval graphs is G. The intersection graphs of arcs of a
circle A circle is a shape consisting of all point (geometry), points in a plane (mathematics), plane that are at a given distance from a given point, the Centre (geometry), centre. The distance between any point of the circle and the centre is cal ...
form
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. Formally, let :I_1, I ...
s, 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 tree In graph theory, a caterpillar or caterpillar tree is a tree (graph theory), tree in which all the Vertex (graph theory), vertices are within distance 1 of a central Path graph, path. Caterpillars were first studied in a series of papers by Har ...
s.


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 In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...
; conversely, the proper interval graphs are exactly the claw-free interval graphs. However, there exist claw-free graphs that are not interval graphs. An interval graph is called q-proper if there is a representation in which no interval is contained by more than q others. This notion extends the idea of proper interval graphs such that a 0-proper interval graph is a proper interval graph. An interval graph is called p-improper if there is a representation in which no interval contains more than p others. This notion extends the idea of proper interval graphs such that a 0-improper interval graph is a proper interval graph. An interval graph is k-nested if there is no chain of length k+1 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 The RAND Corporation, doing business as RAND, is an American nonprofit global policy think tank, research institute, and public sector consulting firm. RAND engages in research and development (R&D) in several fields and industries. Since the ...
'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 Victor LaRue Klee, Jr. (September 18, 1925 – August 17, 2007) was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of ...
. Cohen applied interval graphs to mathematical models of
population biology The term population biology has been used with different meanings. In 1971, Edward O. Wilson ''et al''. used the term in the sense of applying mathematical models to population genetics, community ecology, and population dynamics. Alan Hasting ...
, specifically
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. Interval graphs are used to represent
resource allocation In economics, resource allocation is the assignment of available resources to various uses. In the context of an entire economy, resources can be allocated by various means, such as markets, or planning. In project management, resource allocatio ...
problems in
operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...
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 Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an ''interval'' describing the time in which it needs to be processed b ...
for more information. 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 ...
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 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 p ...
by a
greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...
algorithm that colors the intervals in sorted order by their left endpoints. Other applications include genetics,
bioinformatics Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
, 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 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. Interval graphs also play an important role in temporal reasoning.


Interval completions and pathwidth

If G is an arbitrary graph, an interval completion of G is an interval graph on the same vertex set that contains G 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 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.


Combinatorial enumeration

The number of connected interval graphs on n unlabeled vertices, for n=1, 2, 3, \dots, is: :1, 1, 2, 5, 15, 56, 250, 1328, 8069, 54962, 410330, 3317302, ... Without the assumption of connectivity, the numbers are larger. The number of interval graphs on n unlabeled vertices, not necessarily connected, is: :1, 2, 4, 10, 27, 92, 369, 1807, 10344, 67659, 491347, 3894446, ... These numbers exhibit faster than
exponential growth Exponential growth occurs when a quantity grows as an exponential function of time. The quantity grows at a rate directly proportional to its present size. For example, when it is 3 times as big as it is now, it will be growing 3 times as fast ...
: the number of interval graphs on 3n unlabeled vertices is at least n!/3^. Because of this fast growth rate, the interval graphs do not have bounded twin-width.


Notes


References

* * * * * * * * * * * * * * * * * * * * * * * * * * * * *


External links

* * {{DEFAULTSORT:Interval Graph Perfect graphs Intersection classes of graphs Geometric graphs