User:Katherine H. Chiang/sandbox

This is the user sandbox of Katherine H. Chiang. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that overlap.

Definition

Let {I₁, I₂, ..., I_n} ⊂ P(R) be a set of intervals.

The corresponding interval graph is G = (V, E), where

V = {I₁, I₂, ..., I_n}, and
{I_α, I_β} ∈ E if and only if I_α ∩ I_β ≠ ∅.

From this construction one can verify a common property held by all interval graphs. That is, graph G is an interval graph if and only if the maximal cliques of G can be ordered M₁, M₂, ..., 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,^[1] i.e., there exists a linear order of its maximal cliques such that for each vertex v, all maximal cliques containing v are consecutive.

Efficient recognition algorithms

Several algorithms have been designed to recognize interval graphs in O(|V|+|E|) (linear) time. 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.^[1]^[2]

All of the algorithms above rely on seeking an ordering of the maximal cliques of G that is consecutive with respect to vertex inclusion, and the precomputation of all maximal cliques is required. A simpler off-line recognition algorithm was provided by W. L. Hsu (1992) which directly places the intervals without precomputing maximal cliques^[3].

Habib et al.'s Algorithm

Hsu's Algorithm

The algorithm consists of four main steps:

Compute a cardinality lexicographic ordering (CLO) for G. If G is not chordal, stop.

 1 function CLO(G(V, E)):
 2 ( ω^-1(1), ω^-1(2),..., ω^-1(n) ) := sort V by their degree in descending order;
 3 create a list L of sets with ( ω^-1(1), ω^-1(2),..., ω^-1(n) ) as the only set in it;
 4 /* each set in L is kept as a doubly linked list */
 5 for i := 1 to n do
 6    begin
 7        v := the first element of the first set in L;
 8        remove v from L;
 9        π(i) := v;
 10       split each L_j ∈ L into { N(v) ∩ L_j || L_j \ N(v) };
 11       /* the ω order should remain inside each {N(v) ∩ L_j} and {L_j \ N(v)} */
 12       remove empty sets;
 13   end
 14 return ( π(1), π(2),..., π(n) );

Construct subgraph G".

In the subgraph, each pair of vertices connected with an edge are strictly adjacent, i.e., the two edges are adjacent but each has a neighbor not adjacent to the other vertice.

V" := V

E" := { (u, v) | u, v ∈ D, π^-1(u) < π^-1(v), f(u) ∉ N(v)}

D := V - S; S is the set of simplicial vertices in G.

f(u) := u's neighbor vertex with the smallest π-index.

 1 function G construction((π(1), π(2),..., π(n)), (N(1), N(2),..., N(n))): // N(i) is the neighbor of π(i).
 2 keep two arrays with n elements: 
   initialize all n elements of count[n] to FALSE;
   initialize all n elements of largestN[n] to 0;
 3 for i := 1 to n do
 4    begin
 5        for j := 1 to sizeof N(i) do:
 6           begin 
 7               largestN[N(i)[j]] := i;
 8           end
 9        for j := 1 to sizeof N(i) do:
 10          begin
 11              if count[N(i)[j]] equals FALSE do:
 12                    count[N(i)[j]] := TRUE;
 13                    /* the vertices turned to TRUE in this iteration make up U(π(i)) = {u | f(u) = π(i)} */
 14                    for k := [N(i)[j]] + 1 to n do:
 15                       begin
 16                           if largestN[k] != i do:
 17                               E" += (N(i)[j], k);
 18                       end
 19               endif
 20          end 
 21    end
 22 return E";

Compose an S-decomposition tree of G based on the connected components of G".

First, we need to obtain the containment relationship of the intervals. The Hasse diagram is built at the same time. In the Hasse diagram, vertices strictly adjacent to each other are grouped and treated as one vertex. This can be done by inserting additional steps into last procedure.

(Two lenth-n arrays are added, one integer NewVertex[n] is initialized to NewVertex [ i ] = i; another boolean connected [n] is initialized to FALSE. A counter is kept to record the largest vertex index till now.)

 17  E" += (N(i)[j], k);

 1   if (connected[N(i)[j]] == TRUE) do
 2       connected[k] = TRUE;
 3       NewVertex[k] = NewVertex[N(i)[j]];
 4   endif
 5   else if (connected[k] == TRUE) do
 6       connected[N(i)[j]] = TRUE;
 7       NewVertex[N(i)[j]] = NewVertex[k];
 8   end elseif
 9   else do
 10      connected[N(i)[j]] = connected[k] = TRUE;
 11      NewVertex[N(i)[j]] = NewVertex[k] = counter++;
 12  end else

Then we can get the S-decomposition tree. One thing to note is that we need to avoid cycle in G".

Test each S-prime component to see if it is an interval graph.

This can be done by truly building the true interval graph; first adding the non-simplicial vertices, then adding the simplicial vertices through a linear scan.

Related families of graphs

Interval graphs are chordal graphs and hence perfect graphs.^[1]^[2] Their complements belong to the class of comparability graphs,^[4] and the comparability relations are precisely the interval orders.^[1]

The interval graphs that have an interval representation in which every two intervals are either disjoint or nested are the trivially perfect 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. Every proper interval graph is a claw-free graph. However, the converse is not true. Every claw-free graph is not necessarily a proper interval graph.^[5] If the collection of segments in question is a set, i.e., no repetitions of segments is allowed, then the graph is unit interval graph if and only if it is proper interval graph. ^{[citation needed]}

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 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.^[6]

The connected triangle-free interval graphs are exactly the caterpillar trees.^[7]

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

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.^[10] Interval graphs are used to represent resource allocation problems in operations research and scheduling theory. Each interval represents a request for a resource 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.^[11] Interval graphs also play an important role in temporal reasoning.^[12]

Notes

^ ^a ^b ^c ^d (Fishburn 1985)
^ ^a ^b Golumbic (1980).
^ W. L. Hsu (1992)
^ Gilmore & Hoffman (1964)
^ Faudree, Flandrin & Ryjáček (1997), p. 89.
^ Bodlaender (1998).
^ Eckhoff (1993).
^ Cohen (1978, pp. ix-10)
^ Cohen (1978, pp. 12–33)
^ Zhang et al. (1994).
^ Bar-Noy et al. (2001).
^ Golumbic & Shamir (1993).

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, doi:10.1145/502102.502107.
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.
Hsu, W. L. (1992), "A new test for interval graphs", Lecture Notes in Computer Science, 657 (11–16).
Booth, K. S.; Lueker, G. S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", J. Comput. System Sci., 13 (3): 335–379, doi:10.1016/S0022-0000(76)80045-1.
Cohen, Joel E. (1978). Food webs and niche space. Monographs in Population Biology. Vol. 11. Princeton, NJ: Princeton University Press. pp. xv+1–190. ISBN 978-0-691-08202-8. {{cite book}}: External link in |publisher= (help)
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.
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: 1108–1133, 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 (1–2): 59–84, doi:10.1016/S0304-3975(97)00241-7.
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.

External links

"interval graph". Information System on Graph Class Inclusions. {{cite web}}: External link in |work= (help)

Weisstein, Eric W. "Interval graph". MathWorld.

[Fishburn-1] (Fishburn 1985)

[Golumbic-2] Golumbic (1980).

[3] W. L. Hsu (1992)

[4] Gilmore & Hoffman (1964)

[5] Faudree, Flandrin & Ryjáček (1997), p. 89.

[6] Bodlaender (1998).

[7] Eckhoff (1993).

[8] Cohen (1978, pp. ix-10)

[9] Cohen (1978, pp. 12–33)

[10] Zhang et al. (1994).

[11] Bar-Noy et al. (2001).

[12] Golumbic & Shamir (1993).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]