Drawing Two Posets
share
We investigate the problem of drawing two posets of the same ground set so that one is drawn from left to right and the other one is drawn from the bottom up. The input to this problem is a directed graph G = (V, E) and two sets X, Y with X ∪ Y = E, each of which can be interpreted as a partial order of V. The task is to find a planar drawing of G such that each directed edge in X is drawn as an x-monotone edge, and each directed edge in Y is drawn as a y-monotone edge. Such a drawing is called an xy-planar drawing. Testing whether a graph admits an xy-planar drawing is NP-complete in general. We consider the case that the planar embedding of G is fixed and the subgraph of G induced by the edges in Y is a connected spanning subgraph of G whose upward embedding is fixed. For this case we present a linear-time algorithm that determines whether G admits an xy-planar drawing and, if so, produces an xy-planar polyline drawing with at most three bends per edge.
READ FULL TEXT