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.
