View source for Interval graph

{{Short description|Intersection graph for intervals on the real number line}}
{{Distinguish|D-interval hypergraph}}
[[Image:Interval graph.svg|thumb|upright=1.35|Seven intervals on the real line and the corresponding seven-vertex interval graph.]]
In [[graph theory]], an '''interval graph''' is an [[undirected graph]] formed from a set of [[Interval (mathematics)|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 graph]]s and [[perfect graph]]s. 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 graph]]s, graphs defined in the same way from a set of [[unit interval]]s.

These graphs have been used to model [[food web]]s, 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 {{mvar|G}} formed from a family of intervals
:<math>S_i,\quad i=0,1,2,\dots</math>
by creating one vertex {{mvar|v{{sub|i}}}} for each interval {{mvar|S{{sub|i}}}}, and connecting two vertices {{mvar|v{{sub|i}}}} and {{mvar|v{{sub|j}}}} by an edge whenever the corresponding two sets have a nonempty intersection. That is, the edge set of {{mvar|G}} is
:<math>E(G)=\{(v_i,v_j)\mid S_i\cap S_j\ne\emptyset\}.</math>
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.{{sfnp|Lekkerkerker|Boland|1962}}

Other characterizations:

* A graph is an interval graph if and only if its maximal [[Clique (graph theory)|cliques]] can be ordered <math>M_1,M_2,\dots,M_k</math> 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 <math>v\in M_i\cap M_k</math> with <math>i<k</math>, it is also the case that <math>v\in M_j</math> whenever <math>i<j<k</math>.<ref>{{harvtxt|Fulkerson|Gross|1965}}; {{harvtxt|Fishburn|1985}}</ref>
* A graph is an interval graph if and only if it does not contain the [[cycle graph]] <math>C_4</math> as an [[induced subgraph]] and is the complement of a [[comparability graph]].{{sfnp|Gilmore|Hoffman|1964}}

Various other characterizations of interval graphs and variants have been described.<ref>{{harvtxt|McKee|McMorris|1999}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}</ref>

== Efficient recognition algorithm ==

Determining whether a given graph <math>G=(V,E)</math> is an interval graph can be done in <math>O(|V|+|E|)</math> time by seeking an ordering of the maximal cliques of <math>G</math> 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.{{sfnp|Hsu|1992}}

The original linear time recognition algorithm of {{harvtxt|Booth|Lueker|1976}} is based on their complex [[PQ tree]] data structure, but {{harvtxt|Habib|McConnell|Paul|Viennot|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 graph|chordal]] and its [[complement (graph theory)|complement]] is a [[comparability graph]].<ref>{{harvtxt|Fishburn|1985}}; {{harvtxt|Golumbic|1980}}</ref>
A similar approach using a 6-sweep LexBFS algorithm is described in {{harvtxt|Corneil|Olariu|Stewart|2009}}.

==Related families of graphs==

By the characterization of interval graphs as AT-free chordal graphs,{{sfnp|Lekkerkerker|Boland|1962}} interval graphs are [[strongly chordal graph]]s and hence [[perfect graph]]s. Their [[complement graph|complements]] belong to the class of [[comparability graph]]s,{{sfnp|Gilmore|Hoffman|1964}} and the comparability relations are precisely the [[interval order]]s.{{sfnp|Fishburn|1985}}

From the fact that a graph is an interval graph if and only if it is [[Chordal graph|chordal]] and its [[complement (graph theory)|complement]] is a [[comparability graph]], it follows that 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 graph]]s.

A graph has [[boxicity]] at most one if and only if it is an interval graph; the boxicity of an arbitrary graph <math>G</math> 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 <math>G</math>.

The intersection graphs of [[arc (geometry)|arc]]s of a [[circle]] form [[circular-arc graph]]s, a class of graphs that contains the interval graphs. The [[trapezoid graph]]s, 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 graph|triangle-free]] interval graphs are exactly the [[caterpillar tree]]s.{{sfnp|Eckhoff|1993}}

=== Proper interval graphs ===
{{main|Proper interval graph}}
[[Proper interval graph]]s are interval graphs that have an interval representation in which no interval [[Subset|properly contains]] any other interval; [[unit interval graph]]s 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.<ref>{{harvtxt|Roberts|1969}}; {{harvtxt|Gardi|2007}}</ref> 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.{{sfnp|Faudree|Flandrin|Ryjáček|1997|p=89}}

An interval graph is called <math>q</math>-proper if there is a representation in which no interval is contained by more than <math>q</math> others. This notion extends the idea of proper interval graphs such that a 0-proper interval graph is a proper interval graph.{{sfnp|Proskurowski|Telle|1999}}
An interval graph is called <math>p</math>-improper if there is a representation in which no interval contains more than <math>p</math> others. This notion extends the idea of proper interval graphs such that a 0-improper interval graph is a proper interval graph.{{sfnp|Beyerl|Jamison|2008}}
An interval graph is <math>k</math>-nested if there is no chain of length <math>k+1</math> of intervals nested in each other. This is a generalization of proper interval graphs as 1-nested interval graphs are exactly proper interval graphs.{{sfnp|Klavík|Otachi|Šejnoha|2019}}

==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 [[D. R. Fulkerson|Delbert Fulkerson]] and (recurring visitor) [[Victor Klee]].{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false ix–10]}} Cohen applied interval graphs to [[mathematical biology|mathematical models]] of [[population biology]], specifically [[food web]]s.{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false 12–33]}}

Interval graphs are used to represent [[resource allocation]] problems in [[operations research]] and [[scheduling (computing)|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 (graph theory)|independent set problem]] for the graph represents the problem of finding the best subset of requests that can be satisfied without conflicts.{{sfnp|Bar-Noy|Bar-Yehuda|Freund|Naor|2001}} 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.{{sfnp|Cormen|Leiserson|Rivest|Stein|2001|p=379}}

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.{{sfnp|Zhang|Schon|Fischer|Cayanis|1994}} Interval graphs also play an important role in temporal reasoning.{{sfnp|Golumbic|Shamir|1993}}

==Interval completions and pathwidth==
If <math>G</math> is an arbitrary graph, an '''interval completion''' of <math>G</math>  is an interval graph on the same vertex set that contains <math>G</math> as a subgraph. The parameterized version of interval completion (find an interval supergraph with {{mvar|k}} additional edges) is [[Parameterized complexity|fixed parameter tractable]], and moreover, is solvable in parameterized subexponential time.{{sfnp|Villanger|Heggernes|Paul|Telle|2009}}{{sfnp|Bliznets|Fomin|Pilipczuk|Pilipczuk|2014}}

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 <math>G</math> is the same as the smallest pathwidth of an interval graph that contains <math>G</math> as a subgraph.{{sfnp|Bodlaender|1998}}

==Combinatorial enumeration==
The number of connected interval graphs on <math>n</math> unlabeled vertices, for <math>n=1, 2, 3, \dots</math>, is:{{sfnp|Hanlon|1982|loc=Table VIII, p. 422}}
:1, 1, 2, 5, 15, 56, 250, 1328, 8069, 54962, 410330, 3317302, ... {{OEIS|A005976}}
Without the assumption of connectivity, the numbers are larger. The number of interval graphs on <math>n</math> unlabeled vertices, not necessarily connected, is:{{sfnp|Hanlon|1982|loc=Table VII, p. 421}}
:1, 2, 4, 10, 27, 92, 369, 1807, 10344, 67659, 491347, 3894446, ... {{OEIS|A005975}}

These numbers exhibit faster than [[exponential growth]]: the number of interval graphs on <math>3n</math> unlabeled vertices is at least <math>n!/3^{3n}</math>.{{sfnp|Yang|Pippenger|2017}} Because of this fast growth rate, the interval graphs do not have bounded [[twin-width]].{{sfnp|Bonnet|Kim|Thomassé|Watrigant|2022}}

==Notes==
{{reflist|30em}}

== References ==
{{sfn whitelist |CITEREFCormenLeisersonRivestStein2001}}
{{refbegin|30em}}
*{{citation
 | last1 = Bar-Noy | first1 = Amotz
 | last2 = Bar-Yehuda | first2 = Reuven
 | last3 = Freund | first3 = Ari
 | last4 = Naor | first4 = Joseph (Seffi) | author4-link = Joseph Seffi Naor
 | last5 = Schieber | first5 = Baruch | author5-link = Baruch Schieber
 | title = A unified approach to approximating resource allocation and scheduling
 | journal = [[Journal of the ACM]]
 | year = 2001
 | volume = 48
 | issue = 5
 | pages = 1069–1090
 | doi = 10.1145/502102.502107| citeseerx = 10.1.1.124.9886| s2cid = 12329294 }}
*{{citation
 | last1 = Beyerl | first1 = Jeffery J.
 | last2 = Jamison | first2 = Robert E.
 | arxiv = 1109.6675
 | contribution = Interval graphs with containment restrictions
 | mr = 2489816
 | pages = 117–128
 | series = Congressus Numerantium
 | title = Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing
 | volume = 191
 | year = 2008}}
*{{citation
 | last1 = Bliznets | first1 = Ivan
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Pilipczuk | first3 = Marcin
 | last4 = Pilipczuk | first4 = Michał
 | editor1-last = Schulz | editor1-first = Andreas S.
 | editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner
 | arxiv = 1402.3473
 | contribution = A subexponential parameterized algorithm for proper interval completion
 | doi = 10.1007/978-3-662-44777-2_15
 | pages = 173–184
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proceedings of the 22nd Annual European Symposium on Algorithms (ESA 2014), Wroclaw, Poland, September 8–10, 2014
 | volume = 8737
 | year = 2014| isbn = 978-3-662-44776-5
 | s2cid = 12385294}}
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | doi = 10.1016/S0304-3975(97)00228-4
 | issue = 1–2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 1–45
 | title = A partial {{mvar|k}}-arboretum of graphs with bounded treewidth
 | volume = 209
 | year = 1998| hdl = 1874/18312 | hdl-access = free}}
*{{citation
 | last1 = Bonnet | first1 = Édouard
 | last2 = Kim | first2 = Eun Jung | author2-link = Eun Jung Kim (parameterized complexity)
 | last3 = Thomassé | first3 = Stéphan
 | last4 = Watrigant | first4 = Rémi
 | arxiv = 2004.14789
 | doi = 10.1145/3486655
 | issue = 1
 | journal = [[Journal of the ACM]]
 | mr = 4402362
 | page = A3:1–A3:46
 | title = Twin-width I: Tractable FO model checking
 | volume = 69
 | year = 2022}}
*{{citation
 | last1 = Booth | first1 = K. S. | last2 = Lueker | first2 = G. S.
 | title = Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
 | journal = [[Journal of Computer and System Sciences]]
 | volume = 13
 | pages = 335–379
 | year = 1976
 | doi = 10.1016/S0022-0000(76)80045-1
 | issue = 3| doi-access = free
 }}
*{{citation
 | last1 = Brandstädt
 | first1 = A.
 | last2 = Le
 | first2 = V.B.
 | last3 = Spinrad
 | first3 = J.P.
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 978-0-89871-432-6
 | url-access = registration
 | url = https://archive.org/details/graphclassessurv0000bran}}
*{{citation|year=1978|last=Cohen|first=Joel E.|authorlink=Joel E. Cohen|title=Food webs and niche space|series=Monographs in Population Biology|volume=11|issue=11|pages=1–189|location=Princeton, NJ|publisher=Princeton University Press|pmid=683203|isbn=978-0-691-08202-8}}
*{{Introduction to Algorithms|edition=2|mode=cs2}}
*{{citation
 | last1 = Corneil | first1 = Derek | author1-link = Derek Corneil
 | last2 = Olariu | first2 = Stephan
 | last3 = Stewart | first3 = Lorna | author3-link = Lorna Stewart
 | issue = 4
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | pages = 1905–1953
 | title = The LBFS structure and recognition of interval graphs
 | volume = 23
 | year = 2009
 | doi = 10.1137/S0895480100373455}}
*{{citation
 | last = Eckhoff | first = Jürgen
 | doi = 10.1002/jgt.3190170112
 | issue = 1
 | journal = [[Journal of Graph Theory]]
 | pages = 117–127
 | title = Extremal interval graphs
 | volume = 17
 | year = 1993}}
*{{citation
 | last1 = Faudree | first1 = Ralph | author1-link = Ralph Faudree
 | last2 = Flandrin | first2 = Evelyne
 | last3 = Ryjáček | first3 = Zdeněk
 | doi = 10.1016/S0012-365X(96)00045-3
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 87–147
 | title = Claw-free graphs — A survey
 | volume = 164
 | year = 1997
 | mr = 1432221| doi-access = free
 }}
*{{citation|last=Fishburn|first=Peter C.|authorlink=Peter C. Fishburn|year=1985|title=Interval orders and interval graphs: A study of partially ordered sets|series=Wiley-Interscience Series in Discrete Mathematics|location=New York|publisher=John Wiley & Sons}}
*{{citation
 | author1-link = D. R. Fulkerson | last1 = Fulkerson | first1 = D. R. 
 | last2 = Gross | first2 = O. A.
 | title = Incidence matrices and interval graphs
 | journal = [[Pacific Journal of Mathematics]]
 | volume = 15
 | issue = 3 | pages = 835–855
 | year = 1965 | doi=10.2140/pjm.1965.15.835| doi-access = free}}
*{{citation
 | last         = Gardi  | first        = Frédéric
 | title        = The Roberts characterization of proper and unit interval graphs
 | date         = 2007
 | journal      = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume       = 307
 | issue        = 22
 | pages        = 2906–2908
 | doi          = 10.1016/j.disc.2006.04.043| doi-access= 
 }}
*{{citation
 | last1 = Gilmore | first1 = P. C.
 | last2 = Hoffman | first2 = A. J.
 | title = A characterization of comparability graphs and of interval graphs
 | journal = Canadian Journal of Mathematics
 | volume = 16
 | pages = 539–548
 | year = 1964
 | doi = 10.4153/CJM-1964-055-5| doi-access = free
 }}
*{{citation
 | last = Golumbic | first = Martin Charles | author-link = Martin Charles Golumbic
 | title = Algorithmic Graph Theory and Perfect Graphs
 | publisher = Academic Press
 | year = 1980
 | isbn = 978-0-12-289260-8}}
*{{citation
 | last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic
 | last2 = Shamir | first2 = Ron | author2-link = Ron Shamir
 | title = Complexity and algorithms for reasoning about time: a graph-theoretic approach
 | journal = [[Journal of the ACM]]
 | volume = 40
 | issue = 5 | pages = 1108–1133
 | year = 1993 | doi=10.1145/174147.169675| citeseerx = 10.1.1.35.528| s2cid = 15708027 }}
*{{citation
 | last1 = Habib | first1 = Michel | last2 = McConnell | first2 = Ross
 | last3 = Paul | first3 = Christophe | last4 = Viennot | first4 = Laurent
 | title = Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | volume = 234
 | issue = 1–2 | pages = 59–84
 | year = 2000
 | url = http://www.cs.colostate.edu/~rmm/lexbfs.ps
 | doi = 10.1016/S0304-3975(97)00241-7| doi-access = free}}
*{{citation
 | last = Hanlon | first = Phil
 | doi = 10.2307/1998705
 | issue = 2
 | journal = Transactions of the American Mathematical Society
 | jstor = 1998705
 | mr = 662044
 | pages = 383–426
 | title = Counting interval graphs
 | volume = 272
 | year = 1982| doi-access = free
 }}
*{{citation
 | last = Hsu | first = Wen-Lian
 | editor-last = Mayr | editor-first = Ernst W.
 | contribution = A simple test for interval graphs
 | doi = 10.1007/3-540-56402-0_31
 | pages = 11–16
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 19–20, 1992, Proceedings
 | volume = 657
 | year = 1992| isbn = 978-3-540-56402-7
 }}
*{{citation
 | last1 = Klavík | first1 = Pavel
 | last2 = Otachi | first2 = Yota
 | last3 = Šejnoha | first3 = Jiří
 | arxiv = 1510.03998
 | doi = 10.1007/s00453-018-0481-y
 | issue = 4
 | journal = [[Algorithmica]]
 | mr = 3936165
 | pages = 1490–1511
 | title = On the classes of interval graphs of limited nesting and count of lengths
 | volume = 81
 | year = 2019| s2cid = 254028486
 }}
*{{citation
 | last1 = Lekkerkerker | first1 = C. G. | author1-link = Gerrit Lekkerkerker
 | last2 = Boland | first2 = J. C.
 | title = Representation of a finite graph by a set of intervals on the real line 
 | journal = [[Fundamenta Mathematicae]]
 | volume = 51
 | pages = 45–64
 | year = 1962
| doi = 10.4064/fm-51-1-45-64 
 | doi-access = free}}
*{{citation
 | last1 = McKee | first1 = Terry A.
 | last2 = McMorris | first2 = F. R.
 | title = Topics in Intersection Graph Theory
 | publisher = SIAM Monographs on Discrete Mathematics and Applications 
 | year = 1999
 | isbn = 978-0-89871-430-2}}
*{{citation|last1=Proskurowski|first1=Andrzej|last2=Telle|first2=Jan Arne|title=Classes of graphs with restricted interval models|journal=Discrete Mathematics & Theoretical Computer Science|date=1999|volume=3|issue=4|pages=167–176|citeseerx=10.1.1.39.9532}}
*{{citation
 | last = Roberts | first = F. S. | author-link = Fred S. Roberts
 | editor-last = Harary | editor-first = Frank | editor-link = Frank Harary
 | chapter = Indifference graphs
 | title = Proof Techniques in Graph Theory
 | pages = 139–146
 | year = 1969
 | isbn = 978-0123242600
 | oclc = 30287853
 | publisher = [[Academic Press]]
 | location = [[New York, NY]]}}
*{{citation
 | last1 = Villanger | first1 = Yngve 
 | last2 = Heggernes | first2 = Pinar | author2-link = Pinar Heggernes
| last3 = Paul | first3 = Christophe
| last4 = Telle | first4 = Jan Arne
| doi = 10.1137/070710913
 | journal = [[SIAM Journal on Computing]]
 | pages = 2007–2020
 | title = Interval completion is fixed parameter tractable
 | volume = 38 | issue = 5
 | year = 2009| citeseerx = 10.1.1.73.8999| s2cid = 8521105 
 }}
*{{citation
 | last1 = Yang | first1 = Joyce C.
 | last2 = Pippenger | first2 = Nicholas | author2-link = Nick Pippenger
 | doi = 10.1090/bproc/27
 | journal = Proceedings of the American Mathematical Society
 | mr = 3613306
 | pages = 1–3
 | series = Series B
 | title = On the enumeration of interval graphs
 | volume = 4
 | year = 2017| s2cid = 38225412
 | arxiv = 1609.02479
 }}
*{{citation
 | last1 = Zhang | first1 = Peisen | last2 = Schon | first2 = Eric A. | last3 = Fischer | first3 = Stuart G.
 | last4 = Cayanis | first4 = Eftihia | last5 = Weiss | first5 = Janie
 | last6 = Kistler | first6 = Susan | last7 = Bourne | first7 = Philip E.
 | title = An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA
 | journal = [[Bioinformatics (journal)|Bioinformatics]]
 | volume = 10
 | issue = 3
 | year = 1994
 | pages = 309–317
 | doi =  10.1093/bioinformatics/10.3.309| pmid = 7922688 }}
{{refend}}

== External links ==
* {{citation | url=http://www.graphclasses.org/classes/gc_234.html | title=interval graph
  | work = Information System on Graph Classes and their Inclusions}}
* {{mathworld | urlname = IntervalGraph | title = Interval graph | mode=cs2}}

{{DEFAULTSORT:Interval Graph}}
[[Category:Perfect graphs]]
[[Category:Intersection classes of graphs]]
[[Category:Geometric graphs]]