
8.4. RESULTS IN THE CONSTRAINED SCENARIOS 267
given overlaps. But this means t o find a layout of the bipartite graph on two straight lines
such that there is no edge crossing. In other words, the problem of reconstructing the two
orders of the intervals in A and B is equivalent to the problem of c omput in g an upright
2-spine, 0-bend drawing of the bipartite graph representing th e overlaps. Waterman and
Griggs study th e properties of thi s bipartit e graph, prove that it is a caterpillar and give a
linear-time algorithm to compute an upright 2-spine, 0-bend drawing.
Remaining in t he case of upright drawings, when the number of spines is greater ...