Boris Klemz and Günter Rote:

Ordered level planarity and geodesic planarity

1. In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), Malmö, Sweden, April 2017, pp. 269–272.
2. to appear in: "Graph Drawing". GD 2017, Proceedings of the 25th International Symposium on Graph Drawing, Boston, September 2017, Revised Selected Papers. Lecture Notes in Computer Science, Springer-Verlag, 2018.

Abstract

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.