Boris Klemz and Günter Rote:

1. Ordered level planarity and geodesic planarity.
   In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), Malmö, Sweden, April 2017, pp. 269–272.  →BibTeX
2. Ordered level planarity, geodesic planarity and bi-monotonicity In: "Graph Drawing and Network Visualization". GD 2017, Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization, Boston, September 2017, Revised Selected Papers. Editors: Frabrizio Frati and Kwan-Liu Ma, Lecture Notes in Computer Science, Vol. 10692, Springer-Verlag, 2018, pp. 440–453, doi:10.1007/978-3-319-73915-1_34. Best paper award.  →BibTeX
3. Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity. ACM Transactions on Algorithms 15 (2019), Article 53, 53:1–53:25. doi:10.1145/3359587 arXiv:1708.07428 [cs.CG].  →BibTeX

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 if there is at most one vertex per level.

Our result has applications to other problems, such as T-Level Planarity, Clustered Level Planarity, and Constrained Level Planarity. We strengthen previous hardness results and solve open questions that were posed by Fulek, Pelsmajer, Schaefer and Štefankovič (2015) and by Angelini, Da Lozzo, Di Battista, Frati and Roselli (2013). In particular, our result implies that a published polynomial algorithm by Katz, Krug, Rutter and Wolff (GD'09) for Manhattan Geodesic Planarity is incorrect unless P=NP.