##
**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 |