Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

Question

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the rectangles using minimum number of colors such that any two overlapping rectangles are assigned different colors.

This problem is known to be NP-hard. Xin Han, Kazuo Iwama, Rolf Klein and Andrezej Lingas (Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs) gave an O(log n) approximation. Is there a better approximation algorithm?

We know that the interval coloring problem is solved in polynomial time by first-fit algorithm by considering intervals according to their left endpoints. However, first-fit online algorithm is 8-competitive when the intervals appear in arbitrary order.

What is the performance of the first-fit algorithm for the rectangle coloring problem? What happens to first-fit algorithm when the rectangles appear according to their left (vertical) sides?

Thanks in advance for any help on this.

Answer 1

As suggested by the other answer, $\Omega(\log n)$ lower bound is not too hard to see. Let us do the sweeping bottom up with a horizontal line. The idea is to build components that require larger and larger number of colors. In particular, let $C(i)$ be a gadget that has a top rectangle with color $i$ (i.e., the first fit would assign it color $i$). Clearly, $C(1)$ is just a single rectangle. The component $C(2)$ is

In general, the component $C(k)$ is a rectangle with $C(1), \ldots, C(k-1)$ hanging below it:

Now, it is easy to verify that a fit-first algorithm with sweeping horizontally from the bottom would use $k$ colors to color $C(k)$. However, the intersection graph of $C(k)$ is just a tree, and it can be colored by $2$ colors. Now, $C(k)$ is just a Fibonacci tree in structure, and as such the number of nodes in it is $2^{O(k)}$, which implies $\Omega( \log n )$ gap.

Since there is a simple algorithm that gets $O( \log n)$ approximation to coloring of rectangles, this might be tight. I don't know.

Answer 2

As far as I know, this is not known. An old paper of Asplund and Grunbaum (1960ish) show that if the clique number is 2, then the chromatic number is at most 6 (and this is tight). I think it should be easy to come up with examples where the gap for first-fit is larger than any constant, since trees can be represented by intersection graph of rectangles, and trees require log n colors by any online algorithm.

Answer 3

I think the Asplund, Grunbaum paper, or later papers also show that that the chromatic number of rectangle intersection graphs is at most O(k^2), where k is the size of the maximum clique... however, there are no known examples that require more than linear in k number of colors.