Interval graph

The interval graph form in graph theory a special class of graphs.

The first mention is made of György Hajós in 1957. Interest in interval graphs was given a significant boost by an advance by Seymour Benzer in 1959, who wanted to test a thesis on the structure of genes . Contemporary applications include scheduling problems , archaeological seriation , behavioral psychology , temporal logic , circuit design, and the Human Genome Project , among others .

An interval graph and an interval model.

definition

Be a graph . Is a family of intervals such that ${\displaystyle G=(V,E)}$ ${\displaystyle {\mathcal {I}}:=\{I_{x}\}_{x\in V}}$

${\displaystyle {\begin{aligned}I_{x}\cap I_{y}\neq \emptyset \Leftrightarrow (x,y)\in E,\end{aligned}}}$

so is called the interval model for . Graphs that have an interval model are called interval graphs. ${\displaystyle {\mathcal {I}}}$ ${\displaystyle G}$

Two examples

Spatial planning

A lot of lectures take place in a time interval . How many rooms are enough if each lecture always takes up its own room while it is taking place? ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle V:=\{v_{1},v_{2}\dots v_{n}\}}$ ${\displaystyle T_{i},i\in \{1,2\dots n\}}$

Consider the interval graph , where hold that . If a room can be assigned to each node in such a way that no neighboring nodes take up the same room, this construction satisfies the requirement that simultaneous lectures get different rooms. Such an occupation of the nodes is a coloring . ${\displaystyle G:=(V,E)}$ ${\displaystyle i\neq j}$ ${\displaystyle (v_{i},v_{j})\in E:\Leftrightarrow T_{i}\cap T_{j}\neq \emptyset }$

In general graphs, the determination of a minimal coloring is an NP-hard problem. In perfect graphs , to which the interval graphs belong, it can be solved in linear time.

Cooling problem

Suppose a lot of substances are known to have to be stored at a temperature between and degrees ( ). How many fridges are enough to store all of them? ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S:=\{s_{1},s_{2}\dots s_{n}\}}$ ${\displaystyle t_{i}}$ ${\displaystyle t_{i}'}$ ${\displaystyle i\in \{1,2\dots n\}}$

Assign the interval to each substance and use the interval graph to denote the node and an edge between two substances if and only if the corresponding intervals have a non-vanishing section. ${\displaystyle T_{i}:=[t_{i},t_{i}']}$ ${\displaystyle G}$ ${\displaystyle s_{i}}$

If there is now a clique of , the intervals will have a common point of intersection due to the Helly property of intervals . A refrigerator that is set to this temperature would then be suitable for storing all of the clique's fabrics. The initial question about refrigerators is reduced to determining a minimum clique coverage in the interval graph . ${\displaystyle C\subseteq S}$ ${\displaystyle G}$ ${\displaystyle \{T_{c}\}_{c\in C}}$ ${\displaystyle \tau _{C}}$ ${\displaystyle \tau _{C}}$ ${\displaystyle G}$

In general graphs, the determination of a minimum click coverage is an NP-hard problem. In circular arc graphs, to which the interval graphs belong, it can be solved in linear time.

Further characterizations

Now let G always be an undirected graph. The equivalence of the following statements is subject to the Gilmore and Hoffman theorem :

• G is an interval graph.
• G is chordal and its complement graph is transitive orientable .
• The maximal cliques of G can be ordered in such a way that for each node the maximal cliques that contain it appear consecutively in the order .

Based on the last characterization, Booth and Lueker specified a recognition algorithm with a linear runtime, for which they introduced the data structure of the PQ trees . Fulkerson and Gross formulated this characterization as a property of so-called clique matrices.

Lekkerkerker and Boland were able to show that the following is also an equivalent characterization of interval graphs:

1. G is chordal and
2. every three nodes of G can be ordered in such a way that each path from the first to the third node passes through a neighbor of the second.

A node triple that does not meet the condition from (2) is called an astroid triple . In such a triple, two nodes are connected by a path that avoids the neighboring nodes of the third. Based on this characterization, they also showed:

• G is an interval graph if for all any of the graphs shown below , , , or as induced subgraphs contains. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle {\text{I}}}$ ${\displaystyle {\text{II}}}$ ${\displaystyle {\text{III}}_{n}}$ ${\displaystyle {\text{IV}}_{n}}$ ${\displaystyle {\text{V}}_{n}}$

The graphs with dashed edges form infinite families, where one can be substituted for the dashed edge for each . For the families and let the accounts of this path be adjacent to the white knots drawn above. The astroid triples are always marked in black. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle P_{n}}$ ${\displaystyle {\text{III}}_{n}}$ ${\displaystyle {\text{IV}}_{n}}$

• Complete list of induced subgraphs prohibited in interval graphs
• 

  ${\displaystyle {\text{I}}}$

• 

  ${\displaystyle {\text{II}}}$

• 

  ${\displaystyle {\text{III}}_{n}}$

• 

  ${\displaystyle {\text{IV}}_{n}}$

• 

  ${\displaystyle {\text{V}}_{n}}$

literature

• Alan Gibbons: Algorithmic Graph Theory . Cambridge University Press, Cambridge Cambridgeshire; New York June 27, 1985, ISBN 978-0-521-28881-1 .

Web links

• Interval graphs in the Information System on Graph Classes and their Inclusions .

Individual evidence

1. ↑ G. Hajös: About a kind of graph . In: Intern. Math. Messages . 11, No. 65, 1957.
2. ↑ Seymour Benzer: On the topology of the genetic fine structure . In: Proceedings of the National Academy of Sciences . 45, No. 11, 1959, p. 1607. PMC 222769 (free full text).
3. ^ David Kendall: Incidence matrices, interval graphs and seriation in archeology . In: Pacific Journal of mathematics . 28, No. 3, 1969, pp. 565-570.
4. ^ Clyde H. Coombs, JE Smith: On the detection of structure in attitudes and developmental processes. . In: Psychological Review . 80, No. 5, 1973, p. 337.
5. ↑ Jürgen Dorn: Temporal reasoning in sequence graphs . In: AAAI . Citeseer, pp. 735-740.
   • Martin Charles Golumbic, Ron Shamir: Complexity and algorithms for reasoning about time: A graph-theoretic approach . In: Journal of the ACM (JACM) . 40, No. 5, 1993, pp. 1108-1133.
6. ^ Richard M. Karp: Mapping the genome: some combinatorial problems arising in molecular biology . In: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing . ACM, pp. 278-285.
7. ↑ Martin Charles Golumbic: Algorithmic graph theory and perfect graphs 1980.
8. ↑ Wen-Lian Hsu, Kuo-Hui Tsai: Linear time algorithms on circular-arc graphs . In: Information Processing Letters . 40, No. 3, November 8, 1991, ISSN  0020-0190 , pp. 123-129. doi : 10.1016 / 0020-0190 (91) 90165-E .
9. ^ PC Gilmore, AJ Hoffman: A characterization of comparability graphs and of interval graphs . In: Canadian Journal of Mathematics . 16, No. 0, Jan. 1, 1964, ISSN  1496-4279 , pp. 539-548. doi : 10.4153 / CJM-1964-055-5 .
10. ↑ Kellogg S. Booth, George S. Lueker: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms . In: Journal of Computer and System Sciences . 13, No. 3, December 1, 1976, ISSN  0022-0000 , pp. 335-379. doi : 10.1016 / S0022-0000 (76) 80045-1 . Retrieved November 21, 2015.
11. ↑ DR Fulkerson, OA Gross: Incidence matrices and interval graphs. . In: Pacific Journal of Mathematics . 15, No. 3, 1965, ISSN  0030-8730 , pp. 835-855.
12. ↑ C. Lekkeikerker, J. Boland: Representation of a finite graph by a set of intervals on the real line . In: Fundamenta Mathematicae . 1, No. 51, 1962, ISSN  0016-2736 , pp. 45-64.