We introduce and study the problem Ordered Level Planarity, which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge is realized as a y-monotone curve. This can be interpreted as a variant of Level Planarity in which the vertices on each level appear in a prescribed total order. We show NP-completeness even for the special case that the number of vertices on each level is bounded by 2 and that the maximum degree is 2. This establishes a tight border of tractability, since the problem is easy it there is at most one vertex per level. Our result has applications to other problems. In particular, it implies that a published polynomial algorithm for Manhattan Geodesic Planarity is incorrect unless P=NP.
Last update: August 15, 2017.