Partial and constrained level planarity

Let G = (V;E) be a directed graph and : V ! [k] := f1; : : : ; kg a level assignment such that ℓ(u) <ℓ(v) for all directed edges (u; v) 2 E. A level planar drawing of G is a drawing of G where each vertex v is mapped to a unique point on the horizontal line i with y-coordinate ℓ(v), and each edge is drawn as a y-monotone curve between its endpoints such that no two curves cross in their interior. In the problem Constrained Level Planarity (CLP for short), we are further given a partial ordering ℓ_i of Vi := 1(i) for i 2 [k], and we seek a level planar drawing where the order of the vertices on i is a linear extension of ℓ_i. A special case of this is the problem Partial Level Planarity (PLP for short), where we are asked to extend a given level-planar drawing H of a subgraph H ⊆ G to a complete drawing G of G without modifying the given drawing, i.e., the restriction of G to H must coincide with H. We give a simple polynomial-time algorithm with running time O(n5) for CLP of single-source graphs that is based on a simplified version of an existing levelplanarity testing algorithm for single-source graphs. We introduce a modified type of PQ-tree data structure that is capable of efficiently handling the arising constraints to improve the running time to O(n + kℓ), where is the size of the constraints. We complement this result by showing that PLP is NP-complete even in very restricted cases. In particular, PLP remains NPcomplete even when G is a subdivision of a triconnected planar graph with bounded degree.