home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17143 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  5.1 KB
  1. Xref: sparky sci.math:17143 comp.theory:2730
  2. Path: sparky!uunet!mcsun!Germany.EU.net!urmel.informatik.rwth-aachen.de!beor!jonas
  3. From: jonas@beor.informatik.rwth-aachen.de (Josef Nelissen)
  4. Newsgroups: sci.math,comp.theory
  5. Subject: SUMMARY: INDEPENDENT SET for two dimensional interval graphs
  6. Date: 18 Dec 92 10:21:14 GMT
  7. Organization: Rechnerbetrieb Informatik - RWTH Aachen
  8. Lines: 105
  9. Distribution: inet
  10. Message-ID: <jonas.724674074@beor>
  11. NNTP-Posting-Host: beor.informatik.rwth-aachen.de
  12. Keywords: INDEPENDENT SET, interval graphs, complexity, graphs
  13.  
  14. Hi netters,
  15. in my original posting I wrote:
  16.  
  17. > I would be very interested to get any pointers/references regarding
  18. > the following problems:
  19. > 
  20. > In a natural extension to the notion of an interval graph, let a two
  21. > dimensional interval graph be the graph whose vertices correspond to a
  22. > (finite) set of two dimensional intervals (rectangles for short) in
  23. > N^2 (or the euclidean plane), and two vertices are adjacent iff the
  24. > intersection of the corresponding rectangles is not empty.
  25. > 
  26. > 1) What is the complexity of the INDEPENDENT SET problem for these graphs
  27. > in general?
  28. > 
  29. > 2) What is the complexity for a graph with the following properties of
  30. > the intervals:
  31. > 
  32. >    Consider a finite irregular grid consisting of linear combinations
  33. >    of (ax + by, cx + dy) for integer constants x,y > 0, integer
  34. >    coefficients a,b,c,d >= 0 with the restrictions ax + by <= R and
  35. >    cx + dy <= S.
  36. >    For each point (m, n) of the grid exist two rectangles of
  37. >    dimensions (x, y) (the constants from above) and (y, x)
  38. >    respectively, whose lower left corner coincedes with (m, n), i.e.
  39. >    the endpoints are (m, n), (m+x, n), (m+x, n+y), (m, n+y) and
  40. >    (m, n), (m+y, n), (m+y, n+x), (m, n+x).
  41. > 
  42. > 
  43. > Any help would be greatly appreciated - I don't even know if this
  44. > class of graphs has been identified before!
  45.  
  46. Of course this class of graphs was discovered before:
  47. Let the boxicity of a graph be the minimum number of dimensions for
  48. which k-dimensional boxes are needed to represent the graph as an
  49. intersection graph of these objects. 
  50. Then this class is the one of boxicity <=2 graphs.
  51.  
  52. As can be easily shown, every graph can be constructed as the interval
  53. graph of boxes of an appropriate dimension, but the determination of
  54. the minimum k is NP-complete, which was shown for k >= 3 by Yannakakis
  55. (The Complexity of the Partial Order Dimension Problem, SIAM J. Alg.
  56. Disc. Math 3, 351-358, 1982) and for k=2 recently by Jan Kratochvil of
  57. Charles University in Prague ("A Special Planar Satisfiability Problem
  58. and a consequence of its NP-completeness", submitted for publication).
  59.  
  60. The INDEPENDENT SET problem is NP-complete for boxicity 2 graphs, as
  61. was shown by Paterson, Tanimato et. al (IPL Vol 12 No 3 June 1981 pp.
  62. 133-137). This result can be extended to the intersection graphs of
  63. unit disks, as shown by Wong and Kuo (IPL Vol 28 No 6, 1988 281-286).
  64. Another reference on unit disk graphs is an article by Clark Colbourn
  65. and Johnson (Discrete math Vol 86, 1990, pp 165-177).
  66.  
  67. Other results and references mentioned in this context are:
  68.  
  69.    1. CLIQUE is easy, say in P, for boxicity 2 graphs because
  70.       rectangles in the plane have the "Helly property"; if there is a
  71.       set which corresponds to a clique, there must be a point of
  72.       common overlap. 
  73.  
  74.    2. One can find the minimum number of disjoint sets (of vertices) in
  75.       which a (one-dimensional) interval graph can be partitioned in
  76.       O(nlogn) by some sort of sweep-line-algorithm on the interval
  77.       representation. 
  78.  
  79.    3. The INDEPENDENT SET problem for planar segments is treated in a
  80.       joint paper of Kratochvil and Nesetril (Comm. Math. Univ. Carol.
  81.       31(1990), 85-93)
  82.  
  83.    4. The INDEPENDENT Set problem for other geometric objects is
  84.       treated in an article by T. Asano ("Difficulty of the Maximum
  85.       Independent Set Problem on Graphs of Geometric Objects" in Graph
  86.       Theory, Combinatorics and Applications; Alavi Y. et al. (eds.),
  87.       1988, pp. 9-18)
  88.  
  89. Other references concerning interval graphs are
  90.  
  91.     a) Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Academic
  92.        Press, 1980 
  93.  
  94.     b) Golumbic, M.C.: Interval Graphs and Related Topics, Discrete
  95.        Mathematics, Vol. 55, pp. 113-121, 1985
  96.  
  97.     c) Cozzens, M.B.: Higher and Multi-dimensional Analogues of Interval
  98.        Graphs, Ph.D. thesis, Dept. of Mathematics, Rutgers University,
  99.        New Jersey, 1981
  100.  
  101. Applications for interval graphs can be found in
  102.  
  103.     i) Roberts, F.S.: Discrete Mathematical Models, Prentice-Hall,
  104.        1976
  105.  
  106.    ii) Roberts, F.S.: Graph Theory and its Applications to Problems of
  107.        Society, NSF-CBSM Monograph No.29, SIAM Publications,
  108.        Philadelphia, PA, 1978 
  109.  
  110. I've got no responses concerning my second question, so I will have to
  111. find out myself :-)
  112.  
  113. Many thanks to all who responded, Josef
  114. -- 
  115. Josef Nelissen, Lehrstuhl fuer Angewandte Mathematik, insbesondere Informatik,
  116. RWTH-Aachen, Ahornstr. 55, W-5100 Aachen, Germany, Tel. +49 241/80-21060,
  117. FAX +49 241/80-21079, e-mail jonas@beor.informatik.rwth-aachen.de
  118. * To know everything would be impractical. The access time would be enormous. *
  119.