2
$\begingroup$

Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously respects the constraint that no two overlapping intervals are put into the same row, but it is hard to read because the number of rows is $O(\mathrm{\#\,\,of\,\,intervals})$.

In general, I think the minimum number of rows can be calculated by finding the size of the largest clique in the graph whose nodes are intervals that has an edge iff two intervals overlap. Is there an efficient (polynomial-time, approximate if necessary) algorithm, that, given a set of integer intervals, returns a minimum sized partition of the intervals into "y-axis values" such that no two elements of a subset overlap?

I suspect this problem is equivalent to the following (but disregard this if you disagree): is there an efficient way to compute an exact vertex cover $C$ of an interval graph $G = (V, E)$ such that $\forall I \in C. I^2 \cap E = \emptyset$ and $|C|$ is minimized? It seems like this is closely related to the maximum independent set problem.

A visualization of overlapping intervals

$\endgroup$
2
$\begingroup$

This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. According to these lecture notes there is a polynomial-time greedy algorithm for coloring interval graphs based on the fact that every interval graph has a perfect elimination ordering.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.