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.
Last update: November 25, 2019.