Interval graph
Seven intervals on the real line and the corresponding seven-vertex interval graph.
In graph theory, an interval graph is the intersection graph of a family of intervals on the real line. It has one vertex for each interval in the family, and an edge between vertices whose intervals intersect.
Contents
1 Definition
2 Characterizations
3 Efficient recognition algorithm
4 Related families of graphs
4.1 Proper Interval Graphs
4.2 Improper Interval Graphs
4.3 K-nested Interval Graphs
5 Applications
6 Interval completions and pathwidth
7 Notes
8 References
9 External links
Definition
Formally, an interval graph is an undirected graph G formed from a family of intervals
Si, i = 0, 1, 2, ...
by creating one vertex vi for each interval Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection, that is, the edge set of G is
E(G) = Si ∩ Sj ≠ ∅.
Characterizations
Three vertices form an asteroidal triple in a graph G 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 of G can be ordered M1, M2, ..., Mk such that for any v ∈ Mi ∩ Mk, where i < k, it is also the case that v ∈ Mj for any Mj, 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 C4 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]
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.[citation needed]
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).
Related families of graphs
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
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]
Improper Interval Graphs
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]
K-nested Interval Graphs
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]
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 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]
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 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]
Notes
^ ab Lekkerkerker & Boland (1962)
^ abc (Fishburn 1985)
^ Fulkerson & Gross (1965)
^ ab 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..mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em
^ 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).
References
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.
Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał (2014), "A subexponential parameterized algorithm for proper interval completion", in Schulz, Andreas S.; Wagner, Dorothea, 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.
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.
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 0-89871-432-X.
Cohen, Joel E. (1978), Food webs and niche space, Monographs in Population Biology, 11, Princeton, NJ: Princeton University Press, ISBN 978-0-691-08202-8
Corneil, Derek; Olariu, Stephan; Stewart, Lorna (2009), "The LBFS structure and recognition of interval graphs", SIAM Journal on Discrete Mathematics, 23 (4): 1905–1953.
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 0-12-289260-7.
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.
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: 59–84, doi:10.1016/S0304-3975(97)00241-7.
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.
McKee, Terry A.; McMorris, F.R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-430-3.
Roberts, F. S. (1969), "Indifference graphs", in Harary, Frank, 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.
External links
"interval graph". Information System on Graph Classes and their Inclusions.
- Weisstein, Eric W. "Interval graph". MathWorld.
