Complexity Results for Rectangle Intersection and Overlap Graphs.

Abstract

Let R be a family of iso-oriented rectangles in the plane. A graph G = (V, E) is called a rectangle intersection (resp., overlap) graph for R if there is a one-to-one correspondence between V and R such that two vertices in V are adjacent to each other if and only if the corresponding rectangles in R intersect (resp., overlap) each other. It is known that the maximum clique and minimum vertex coloring problems are solvable in polynomial time and NP-hard, respectively, for rectangle intersection graphs. In this paper, we first prove that maximum independent set problem is NP-hard even for both cubic planar rectangle intersection and cubic planar rectangle overlap graphs. We then show the NP-completeness of the vertex coloring problem with three colors for both planar rectangle intersection and planar rectangle overlap graphs even when the degree of every vertex is limited to four. Finally we described how to find, in polynomial time, a maximum clique of a rectangle overlap graph.