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.

- Definition
- Characterizations
- Efficient recognition algorithm
- Related families of graphs
- Proper Interval Graphs
- Improper Interval Graphs
- K-nested Interval Graphs
- Applications
- Interval completions and pathwidth
- Notes
- References
- External links

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.

An interval graph is an undirected graph *G* formed from a family of intervals

*S*_{i},*i*= 0, 1, 2, ...

by creating one vertex *v*_{i} for each interval *S*_{i}, and connecting two vertices *v*_{i} and *v*_{j} by an edge whenever the corresponding two sets have a nonempty intersection, that is, the edge set of *G* is

*E*(*G*) = {{*v*_{i},*v*_{j}} |*S*_{i}∩*S*_{j}≠ ∅}.

Three 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.
^{ [1] }

Other characterizations:

- A graph is an interval graph if and only if its maximal cliques can be ordered
*M*_{1},*M*_{2}, ...,*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*.^{ [2] }

- A graph is an interval graph if and only if the edge clique cover of all of its maximal cliques can be arranged into a clique path representation.
^{ [3] }

- A graph is an interval graph if and only if it does not contain
*C*_{4}as an induced subgraph and its complement has a transitive orientation.^{ [4] }

Various other characterizations of interval graphs and variants have been described.^{ [5] }^{ [6] }

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 ( Hsu 1992 ).

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.^{ [2] }^{ [7] } A similar approach using a 6-sweep LexBFS algorithm is described in Corneil, Olariu & Stewart (2009).

By the characterization of interval graphs as AT-free chordal graphs,^{ [1] } interval graphs are strongly chordal graphs and hence perfect graphs. Their complements belong to the class of comparability graphs,^{ [4] } and the comparability relations are precisely the interval orders.^{ [2] }

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, we have: A graph and its complement are interval graphs if and only if it 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 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 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.^{ [8] }

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.^{ [9] } 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.^{ [10] }

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.^{ [11] }

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.^{ [12] }

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.^{ [13] }

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.^{ [14] } Cohen applied interval graphs to mathematical models of population biology, specifically food webs.^{ [15] }

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.^{ [16] } 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.^{ [17] }

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.^{ [18] } Interval graphs also play an important role in temporal reasoning.^{ [19] }

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 k additional edges) is fixed parameter tractable, and moreover, is solvable in parameterized subexponential time.^{ [20] }^{ [21] }

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.^{ [22] }

- 1 2 Lekkerkerker & Boland (1962)
- 1 2 3 ( Fishburn 1985 )
- ↑ Fulkerson & Gross (1965)
- 1 2 Gilmore & Hoffman (1964)
- ↑ McKee & McMorris (1999)
- ↑ Brandstädt, Le & Spinrad (1999)
- ↑ Golumbic (1980).
- ↑ Eckhoff (1993).
- ↑ Roberts (1969); Gardi (2007)
- ↑ Faudree, Flandrin & Ryjáček (1997), p. 89.
- ↑ Proskurowski, Andrzej; Telle, Jan Arne (1999). "Classes of graphs with restricted interval models".
*Discrete Mathematics & Theoretical Computer Science*.**3**(4): 167–176. CiteSeerX 10.1.1.39.9532 . - ↑ Beyerl, Jeffrey; Jamison, Robert (2008). "Interval graphs with containment restrictions".
*Congressus Numerantium*.**191**(2008): 117–128. arXiv: 1109.6675 . Bibcode:2011arXiv1109.6675B. - ↑ Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (2015-10-14). "On the Classes of Interval Graphs of Limited Nesting and Count of Lengths". arXiv: 1510.03998 [cs.DM].
- ↑ Cohen (1978 , pp. ix-10 )
- ↑ Cohen (1978 , pp. 12–33 )
- ↑ Bar-Noy et al. (2001).
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990].
*Introduction to Algorithms*(2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. - ↑ Zhang et al. (1994).
- ↑ Golumbic & Shamir (1993).
- ↑ Villanger et al. (2009).
- ↑ Bliznets et al. (2014).
- ↑ Bodlaender (1998).

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. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

In graph theory, the **perfect graph theorem** of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In the mathematical area of graph theory, a **chordal graph** is one in which all cycles of four or more vertices have a *chord*, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called **rigid circuit graphs** or **triangulated graphs**.

In graph theory, a **cograph**, or **complement-reducible graph**, or ** P_{4}-free graph**, is a graph that can be generated from the single-vertex graph

In graph theory, a **circle graph** is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

In graph theory, a **path decomposition** of a graph *G* is, informally, a representation of *G* as a "thickened" path graph, and the **pathwidth** of *G* is a number that measures how much the path was thickened to form *G*. More formally, a path-decomposition is a sequence of subsets of vertices of *G* such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as **interval thickness**, **vertex separation number**, or **node searching number**.

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 of sets that are used to form an intersection representation of them.

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 Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

In graph theory, a **string graph** is an intersection graph of curves in the plane; each curve is called a "string". Given a graph *G*, *G* is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to *G*.

In graph theory, a branch of discrete mathematics, a **distance-hereditary graph** is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In graph theory, a branch of mathematics, a **clique-sum** is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs *G* and *H* each contain cliques of equal size, the clique-sum of *G* and *H* is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A *k*-clique-sum is a clique-sum in which both cliques have at most *k* vertices. One may also form clique-sums and *k*-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation.

In mathematics, a **permutation graph** is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

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 named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as **comparability graphs of trees**, **arborescent comparability graphs**, and **quasi-threshold graphs**.

In the mathematical area of graph theory, an undirected graph *G* is **strongly chordal** if it is a chordal graph and every cycle of even length in *G* has an *odd chord*, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

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

In the mathematical field of graph theory, the **intersection number** of a graph *G* = (*V*,*E*) is the smallest number of elements in a representation of *G* as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover all of the edges of *G*.

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. A graph is a **trapezoid graph** if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988. There exists algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.

In graph theory, a branch of mathematics, an **indifference graph** is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called **unit interval graphs** or **proper interval graphs**; they form a subclass of the interval graphs.

In the mathematical area of graph theory, a **chordal bipartite graph** is a bipartite graph *B* = (*X*,*Y*,*E*) in which every cycle of length at least 6 in *B* has a *chord*, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

In the mathematical area of graph theory, an undirected graph *G* is **dually chordal** if the hypergraph of its maximal cliques is a hypertree. The name comes from the fact that a graph is chordal if and only if the hypergraph of its maximal cliques is the dual of a hypertree. Originally, these graphs were defined by maximum neighborhood orderings and have a variety of different characterizations. Unlike for chordal graphs, the property of being dually chordal is not hereditary, i.e., induced subgraphs of a dually chordal graph are not necessarily dually chordal, and a dually chordal graph is in general not a perfect graph. Dually chordal graphs appeared first under the name **HT-graphs**.

- Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch (2001), "A unified approach to approximating resource allocation and scheduling",
*Journal of the ACM*,**48**(5): 1069–1090, CiteSeerX 10.1.1.124.9886 , doi:10.1145/502102.502107, S2CID 12329294 . - Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał (2014), "A subexponential parameterized algorithm for proper interval completion", in Schulz, Andreas S.; Wagner, Dorothea (eds.),
*Proceedings of the 22nd Annual European Symposium on Algorithms (ESA 2014), Wroclaw, Poland, September 8-10, 2014*, Lecture Notes in Computer Science,**8737**, Springer-Verlag, pp. 173–184, arXiv: 1402.3473 , doi:10.1007/978-3-662-44777-2_15, ISBN 978-3-662-44776-5, S2CID 12385294 . - Bodlaender, Hans L. (1998), "A partial
*k*-arboretum of graphs with bounded treewidth",*Theoretical Computer Science*,**209**(1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4, hdl: 1874/18312 . - Booth, K. S.; Lueker, G. S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms",
*J. Comput. Syst. Sci.*,**13**(3): 335–379, doi:10.1016/S0022-0000(76)80045-1 . - Brandstädt, A.; Le, V.B.; Spinrad, J.P. (1999),
*Graph Classes: A Survey*, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6 . - Cohen, Joel E. (1978),
*Food webs and niche space*, Monographs in Population Biology,**11**, Princeton, NJ: Princeton University Press, pp. 1–189, ISBN 978-0-691-08202-8, PMID 683203 - Corneil, Derek; Olariu, Stephan; Stewart, Lorna (2009), "The LBFS structure and recognition of interval graphs",
*SIAM Journal on Discrete Mathematics*,**23**(4): 1905–1953, doi:10.1137/S0895480100373455 . - Eckhoff, Jürgen (1993), "Extremal interval graphs",
*Journal of Graph Theory*,**17**(1): 117–127, doi:10.1002/jgt.3190170112 . - Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey",
*Discrete Mathematics*,**164**(1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221 . - Fishburn, Peter C. (1985),
*Interval orders and interval graphs: A study of partially ordered sets*, Wiley-Interscience Series in Discrete Mathematics, New York: John Wiley & Sons - Fulkerson, D. R.; Gross, O. A. (1965), "Incidence matrices and interval graphs",
*Pacific Journal of Mathematics*,**15**(3): 835–855, doi: 10.2140/pjm.1965.15.835 . - Gardi, Frédéric (2007), "The Roberts characterization of proper and unit interval graphs",
*Discrete Mathematics*,**307**(22): 2906–2908, doi:10.1016/j.disc.2006.04.043 . - Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs",
*Can. J. Math.*,**16**: 539–548, doi:10.4153/CJM-1964-055-5 . - Golumbic, Martin Charles (1980),
*Algorithmic Graph Theory and Perfect Graphs*, Academic Press, ISBN 978-0-12-289260-8 . - Golumbic, Martin Charles; Shamir, Ron (1993), "Complexity and algorithms for reasoning about time: a graph-theoretic approach",
*J. Assoc. Comput. Mach.*,**40**(5): 1108–1133, CiteSeerX 10.1.1.35.528 , doi:10.1145/174147.169675, S2CID 15708027 . - Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing",
*Theor. Comput. Sci.*,**234**(1–2): 59–84, doi:10.1016/S0304-3975(97)00241-7 . - Hsu, Wen-Lian (1992), "A Simple Test for Interval Graphs", in Mayr, Ernst W. (ed.),
*Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 19-20, 1992, Proceedings*, Lecture Notes in Computer Science,**657**, Springer, pp. 11–16, doi:10.1007/3-540-56402-0_31 . - Lekkerkerker, C.G.; Boland, J.C. (1962), "Representation of a finite graph by a set of intervals on the real line",
*Fund. Math.*,**51**: 45–64, doi: 10.4064/fm-51-1-45-64 . - McKee, Terry A.; McMorris, F.R. (1999),
*Topics in Intersection Graph Theory*, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-430-2 . - Roberts, F. S. (1969), "Indifference graphs", in Harary, Frank (ed.),
*Proof Techniques in Graph Theory*, New York, NY: Academic Press, pp. 139–146, ISBN 978-0123242600, OCLC 30287853 . - Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne (2009), "Interval Completion Is Fixed Parameter Tractable",
*SIAM J. Comput.*,**38**(5): 2007–2020, CiteSeerX 10.1.1.73.8999 , doi:10.1137/070710913 . - Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E. (1994), "An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA",
*Bioinformatics*,**10**(3): 309–317, doi:10.1093/bioinformatics/10.3.309, PMID 7922688 .

- "interval graph".
*Information System on Graph Classes and their Inclusions*.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.