From: jonas@beor.informatik.rwth-aachen.de (Josef Nelissen)
Newsgroups: sci.math,comp.theory
Subject: SUMMARY: INDEPENDENT SET for two dimensional interval graphs
Date: 18 Dec 92 10:21:14 GMT
Organization: Rechnerbetrieb Informatik - RWTH Aachen
Distribution: inet
NNTP-Posting-Host: beor.informatik.rwth-aachen.de
Keywords: INDEPENDENT SET, interval graphs, complexity, graphs

Hi netters,
in my original posting I wrote:

> I would be very interested to get any pointers/references regarding
> the following problems:
> 
> In a natural extension to the notion of an interval graph, let a two
> dimensional interval graph be the graph whose vertices correspond to a
> (finite) set of two dimensional intervals (rectangles for short) in
> N^2 (or the euclidean plane), and two vertices are adjacent iff the
> intersection of the corresponding rectangles is not empty.
> 
> 1) What is the complexity of the INDEPENDENT SET problem for these graphs
> in general?
> 
> 2) What is the complexity for a graph with the following properties of
> the intervals:
> 
>    Consider a finite irregular grid consisting of linear combinations
>    of (ax + by, cx + dy) for integer constants x,y > 0, integer
>    coefficients a,b,c,d >= 0 with the restrictions ax + by <= R and
>    cx + dy <= S.
>    For each point (m, n) of the grid exist two rectangles of
>    dimensions (x, y) (the constants from above) and (y, x)
>    respectively, whose lower left corner coincedes with (m, n), i.e.
>    the endpoints are (m, n), (m+x, n), (m+x, n+y), (m, n+y) and
>    (m, n), (m+y, n), (m+y, n+x), (m, n+x).
> 
> 
> Any help would be greatly appreciated - I don't even know if this
> class of graphs has been identified before!

Of course this class of graphs was discovered before:
Let the boxicity of a graph be the minimum number of dimensions for
which k-dimensional boxes are needed to represent the graph as an
intersection graph of these objects. 
Then this class is the one of boxicity <=2 graphs.

As can be easily shown, every graph can be constructed as the interval
graph of boxes of an appropriate dimension, but the determination of
the minimum k is NP-complete, which was shown for k >= 3 by Yannakakis
(The Complexity of the Partial Order Dimension Problem, SIAM J. Alg.
Disc. Math 3, 351-358, 1982) and for k=2 recently by Jan Kratochvil of
Charles University in Prague ("A Special Planar Satisfiability Problem
and a consequence of its NP-completeness", submitted for publication).

The INDEPENDENT SET problem is NP-complete for boxicity 2 graphs, as
was shown by Paterson, Tanimato et. al (IPL Vol 12 No 3 June 1981 pp.
133-137). This result can be extended to the intersection graphs of
unit disks, as shown by Wong and Kuo (IPL Vol 28 No 6, 1988 281-286).
Another reference on unit disk graphs is an article by Clark Colbourn
and Johnson (Discrete math Vol 86, 1990, pp 165-177).

Other results and references mentioned in this context are:

   1. CLIQUE is easy, say in P, for boxicity 2 graphs because
      rectangles in the plane have the "Helly property"; if there is a
      set which corresponds to a clique, there must be a point of
      common overlap. 

   2. One can find the minimum number of disjoint sets (of vertices) in
      which a (one-dimensional) interval graph can be partitioned in
      O(nlogn) by some sort of sweep-line-algorithm on the interval
      representation. 

   3. The INDEPENDENT SET problem for planar segments is treated in a
      joint paper of Kratochvil and Nesetril (Comm. Math. Univ. Carol.
      31(1990), 85-93)

   4. The INDEPENDENT Set problem for other geometric objects is
      treated in an article by T. Asano ("Difficulty of the Maximum
      Independent Set Problem on Graphs of Geometric Objects" in Graph
      Theory, Combinatorics and Applications; Alavi Y. et al. (eds.),
      1988, pp. 9-18)

Other references concerning interval graphs are

    a) Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Academic
       Press, 1980 

    b) Golumbic, M.C.: Interval Graphs and Related Topics, Discrete
       Mathematics, Vol. 55, pp. 113-121, 1985

    c) Cozzens, M.B.: Higher and Multi-dimensional Analogues of Interval
       Graphs, Ph.D. thesis, Dept. of Mathematics, Rutgers University,
       New Jersey, 1981

Applications for interval graphs can be found in

    i) Roberts, F.S.: Discrete Mathematical Models, Prentice-Hall,
       1976

   ii) Roberts, F.S.: Graph Theory and its Applications to Problems of
       Society, NSF-CBSM Monograph No.29, SIAM Publications,
       Philadelphia, PA, 1978 

I've got no responses concerning my second question, so I will have to
find out myself :-)

Many thanks to all who responded, Josef
-- 
Josef Nelissen, Lehrstuhl fuer Angewandte Mathematik, insbesondere Informatik,
RWTH-Aachen, Ahornstr. 55, W-5100 Aachen, Germany, Tel. +49 241/80-21060,
FAX +49 241/80-21079, e-mail jonas@beor.informatik.rwth-aachen.de
* To know everything would be impractical. The access time would be enormous. *