Boris Klemz and Günter Rote:

Ordered level planarity, geodesic planarity and bi-monotonicity

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.
2. to appear 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, Springer-Verlag, 2017, 14 pages.
3. Full version in arXiv:1708.07428 [cs.CG], 25 pages.

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.