3.7.201. Rectangle clique partition

Denotes the fact that, by reduction to the rectangle clique partition problem, deciding whether a constraint has a solution or not was shown to be NP -hard. The rectangle clique partition problem can be described as follows: given a rectangle graph, can its set of vertices be partitioned into k subsets of vertices such that all corresponding induced subgraphs correspond to cliques? A rectangle graph is a graph that can be associated with a set of fixed rectangles whose sides are parallel to the axes of the Β placement space: to each rectangle corresponds a vertex of the rectangle graph, while to each pair of intersecting rectangles corresponds an edge.