<p>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. </p>

CC BY-SA 2.5
2010-12-09T17:22:04.523Z
2010-12-09T17:22:04.523Z
ipsofacto
<p>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. </p>

CC BY-SA 2.5
2010-12-10T22:30:26.817Z
2010-12-10T22:30:26.817Z
ipsofacto
<p>As suggested by the other answer, <span class="math-container">$\Omega(\log n)$</span> 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 <span class="math-container">$C(i)$</span> be a gadget that has a top rectangle with color <span class="math-container">$i$</span> (i.e., the first fit would assign it color <span class="math-container">$i$</span>). Clearly, <span class="math-container">$C(1)$</span> is just a single rectangle. 
The component <span class="math-container">$C(2)$</span> is</p>

<p><a href="https://i.sstatic.net/OHwGK.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/OHwGK.gif" alt=""></a></p>

<p>In general, the component <span class="math-container">$C(k)$</span> is a rectangle with <span class="math-container">$C(1), \ldots, C(k-1)$</span> hanging below it:</p>

<p><a href="https://i.sstatic.net/a1s9H.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/a1s9H.gif" alt=""></a></p>

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

<p>Since there is a simple algorithm that gets <span class="math-container">$O( \log n)$</span> approximation to coloring of rectangles, this might be tight. I don't know.</p>

CC BY-SA 4.0
2010-12-09T21:51:59.510Z
2019-01-07T08:34:00.613Z
2019-01-07T08:34:00.613Z
Sariel Har-Peled
<p>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.</p>

<p>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?</p>

<p>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.</p>

<p>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?</p>

<p>Thanks in advance for any help on this. </p>

<ds.algorithms><approximation-algorithms><cg.comp-geom><graph-colouring><online-algorithms>
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
Soumitra
# Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

(Asked by: username_0 on 2010-12-09)

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.

**Tags:** ds.algorithms, approximation-algorithms, cg.comp-geom, graph-colouring, online-algorithms

---

## 3 answers

### Answer by username_2 on 2010-12-09. Score: 12 | Accepted answer

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

[![](https://i.sstatic.net/OHwGK.gif)](https://i.sstatic.net/OHwGK.gif)

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

[![](https://i.sstatic.net/a1s9H.gif)](https://i.sstatic.net/a1s9H.gif)

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 by username_1 on 2010-12-09. Score: 6

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 by username_1 on 2010-12-10. Score: 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.


---

