Interval graph

Seven intervals on a line and the corresponding interval graph with seven vertices.

An interval graph is the intersection graph of a multiset of intervals on a straight line. It has one vertex for each interval in the set and an edge between each pair of vertices if the corresponding intervals intersect.

Content

Definition

Let be $\{I_{1},I_{2},...,I_{n}\}\subset P(R)$ ${\ displaystyle \ {I_ {1}, I_ {2}, ..., I_ {n} \} \ subset P (R)}$ - many intervals.

The corresponding interval graph is $G=(V,E)$ ${\ displaystyle G = (V, E)}$ where

$V=\{I_{1},I_{2},...,I_{n}\}$ ${\ displaystyle V = \ {I_ {1}, I_ {2}, ..., I_ {n} \}}$ and
$\{I_{\alpha },I_{\beta }\}\in E$ ${\ displaystyle \ {I _ {\ alpha}, I _ {\ beta} \} \ in E}$ , if and only if $I_{\alpha }\cap I_{\beta }\neq \emptyset$ ${\ displaystyle I _ {\ alpha} \ cap I _ {\ beta} \ neq \ emptyset}$ .

From this construction, one can obtain the general properties of interval graphs. So, a graph G is interval if and only if the largest clicks of a graph G can be ordered $M_{1},M_{2},...,M_{k}$ ${\ displaystyle M_ {1}, M_ {2}, ..., M_ {k}}$ so for any $v\in M_{i}\cap M_{k}$ ${\ displaystyle v \ in M_ {i} \ cap M_ {k}}$ where $i<k$ ${\ displaystyle i <k}$ also performed $v\in M_{j}$ ${\ displaystyle v \ in M_ {j}}$ for anyone $M_{j},i\leq j\leq k$ ${\ displaystyle M_ {j}, i \ leq j \ leq k}$ ^[1] .

Effective recognition algorithms

Determine if a graph is $G=(V,E)$ ${\ displaystyle G = (V, E)}$ interval time can be $O(|V|+|E|)$ ${\ displaystyle O (| V | + | E |)}$ by ordering the largest cliques of the graph G.

The initial recognition algorithm for linear time by Booth and Lueker ( Booth, Lueker 1976 ) is based on the complex structure of PQ trees , but Habib, McConnell, Paul and Vienno ( Habib, McConnell, Paul, Viennot 2000 ) showed how to solve the problem easier using lexicographic search in width and based on the fact that a graph is interval if and only if it is chordal and its complement is a graph of comparability ^[1] ^[2] .

Associated Graph Families

Interval graphs are chordal and, therefore, perfect ^[1] ^[2] . Their additions belong to the class of comparability graphs ^[3] , and the comparison relation is precisely the ^[1] .

Interval graphs having an interval representation in which any two intervals are either disjoint or nested are trivial perfect graphs .

Regular interval graphs are interval graphs that have an interval representation in which no interval is a proper subset of any other interval. Unit interval graphs are interval graphs having an interval representation in which each interval has a unit length. Any regular interval graph has no claws . However, the converse is not true - a graph without claws is not necessarily a regular interval graph ^[4] . If the set of segments is a set , that is, the repetition of segments is not allowed, then the graph is a unit interval graph if and only if it is a regular interval graph ^[5] .

The intersection graphs of circular arcs form the graphs of circular arcs - a class of graphs containing interval graphs. Trapezoidal graphs , the intersection of trapezoids, all parallel sides of which lie on two parallel lines, are a generalization of interval graphs.

The path width of the interval graph is one less than the size of the maximum clique (or, equivalently, one less than its chromatic number), and the path width of any graph G is equal to the smallest path width of the interval graph containing G as a subgraph ^[6] .

Related interval graphs without triangles are exactly caterpillar trees ^[7] .

Applications

The mathematical theory of interval graphs was developed with an eye on the applications of researchers from the mathematical division of RAND Corporation , which included young researchers such as and students such as Alan Tucker and , not counting leaders such as Delbert Ray Fulkerson and (frequent guest) ^[8] . Cohen used interval graphs in mathematical models of populations , especially food chains ^[9] .

Other applications include genetics, bioinformatics, and computer science . The search for many segments representing an interval graph can be used as a technique for assembling continuous sequences in DNA ^[10] . Interval graphs are used in the formulation of tasks in operations research and task planning . Each gap represents a request for a resource for a specific period of time. The problem of finding an independent set of maximum graph weight is the problem of finding the best subset of queries that can be performed without conflict ^[11] .

Notes

↑ ¹ ² ³ ⁴ Fishburn, 1985 .
↑ ¹ ² Golumbic, 1980 .
↑ Gilmore, Hoffman, 1964 .
↑ Faudree, Flandrin, Ryjáček, 1997 , p. 89
↑ Roberts, 1969 .
↑ Bodlaender, 1998 .
↑ Eckhoff, 1993 .
↑ Cohen, 1978 ix-10
↑ Cohen, 1978 12-33
↑ Zhang et al., 1994 .
↑ Bar-Noy, Bar-Yehuda, Freund, Naor, 2001 .

Literature

Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber. A unified approach to approximating resource allocation and scheduling // Journal of the ACM. - 2001. - T. 48 , no. 5 . - S. 1069-1090 . - DOI : 10.1145 / 502102.502107 .
Hans L. Bodlaender. A partial k -arboretum of graphs with bounded treewidth // Theoretical Computer Science . - 1998 .-- T. 209 , no. 1-2 . - S. 1-45 . - DOI : 10.1016 / S0304-3975 (97) 00228-4 .
KS Booth, GS Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // J. Comput. System sci. - 1976. - T. 13 , no. 3 . - S. 335-379 . - DOI : 10.1016 / S0022-0000 (76) 80045-1 .
Joel E. Cohen. Food webs and niche space. - Princeton, NJ: Princeton University Press , 1978. - Vol. 11. - P. xv + 1–190. - ISBN 978-0-691-08202-8 .
Eckhoff, Jürgen. Extremal interval graphs // Journal of Graph Theory. - 1993. - T. 17 , no. 1 . - S. 117-127 . - DOI : 10.1002 / jgt . 3190170112 .
Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Claw-free graphs - A survey // Discrete Mathematics. - 1997. - T. 164 , no. 1-3 . - S. 87—147 . - DOI : 10.1016 / S0012-365X (96) 00045-3 .
Peter C. Fishburn. Interval orders and interval graphs: A study of partially ordered sets. - New York, 1985. - (Wiley-Interscience Series in Discrete Mathematics).
DR Fulkerson, OA Gross. Incidence matrices and interval graphs // Pacific Journal of Mathematics. - 1965 .-- T. 15 . - S. 835-855 .
PC Gilmore, AJ Hoffman. A characterization of comparability graphs and of interval graphs // Can. J. Math. - 1964 .-- T. 16 . - S. 539-548 . - DOI : 10.4153 / CJM-1964-055-5 . .
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Martin Charles Golumbic, Ron Shamir. Complexity and algorithms for reasoning about time: a graph-theoretic approach // J. Assoc. Comput. Mach. - 1993 .-- T. 40 . - S. 1108-1133 . .
Michel Habib, Ross McConnell, Christophe Paul, Laurent Viennot. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing // Theor. Comput. Sci .. - 2000. - T. 234 . - S. 59-84 . - DOI : 10.1016 / S0304-3975 (97) 00241-7 .
FS Roberts. Proof Techniques in Graph Theory. - Academic Press, New York, 1969 .-- S. 139-146.
Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler, Philip E. Bourne. An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA // Bioinformatics. - 1994. - T. 10 , no. 3 . - S. 309-317 . - DOI : 10.1093 / bioinformatics / 10.3.309 .

Links

interval graph (unspecified) . Information System on Graph Classes and their Inclusions .
Weisstein, Eric W. Interval graph on Wolfram MathWorld .

[_0bac401f7db4ef5d-1] ¹ ² ³ ⁴ Fishburn, 1985 .

[_d0dc4be937ac5c21-2] ¹ ² Golumbic, 1980 .

[_7124c3ac091a9671-3] Gilmore, Hoffman, 1964 .

[4] Faudree, Flandrin, Ryjáček, 1997 , p. 89

[_1a97c8c1d854f95f-5] Roberts, 1969 .

[_4c88246e850290c8-6] Bodlaender, 1998 .

[_222662cd20c31e49-7] Eckhoff, 1993 .

[8] Cohen, 1978 ix-10

[9] Cohen, 1978 12-33

[_6b38d8dccd004de7-10] Zhang et al., 1994 .

[_098801e6ed9d5b84-11] Bar-Noy, Bar-Yehuda, Freund, Naor, 2001 .