## Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane.(English)Zbl 0548.68067

The graph $$G=(V,E)$$ is an intersection graph if V is a set of rectangles in the (x,y)-plane with sides parallel to the axes, and E contains all pairs of V which have a non-empty intersection. In the sequel, G is an intersection graph with $$| V| =n$$. The paper presents an $${\mathcal O}(n \log n)$$ algorithm for finding the components of G using an iterative procedure based on a well-chosen increasing sequence of y- coordinates and representing the components as they are built up, in a 2- 3-tree. The algorithm is optimal within a constant factor. An extension is given to graphs formed from regular 2m-gons instead of rectangles. An $${\mathcal O}(n \log n)$$ algorithm is given for finding a maximum clique in G. Using the Helly-property it is noted that the problem is equivalent to finding a rectangular region included in the maximum number of rectangles. Here an extension is given to cliques with maximum weight when each vertex of G has a weight $$\geq 0$$. A sketch of a proof is given to show that for each $$k\geq 3$$, k-colorability of G is NP-complete.
Reviewer: F.Göbel

### MSC:

 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C99 Graph theory
Full Text: