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


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