Partial and constrained level planarity

Let G = ( V , E ) be a directed graph and ℓ : V → [ k ] : = { 1 , 2 , … , k } a level assignment such that ℓ ( u ) < ℓ ( v ) for all directed edges ( u , v ) ∈ E . A level-planar drawing of G maps each vertex v to a unique point on the horizontal line ℓ with y -coordinate ℓ ( v ) and each directed edge to a y -monotone Jordan arc between its endpoints such that no two arcs cross in their interior. In the problem Constrained Level Planarity ( CLP for short), we are further given a partial ordering ◁ i of V i : = ℓ − 1 ( i ) for each i ∈ [ k ] , and we seek a level-planar drawing where the linear order ≺ i 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 of 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 ( n 5 ) for CLP of single-source graphs that is based on a simplified version of an existing level-planarity 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 s ) , where s denotes 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 NP -complete even when G has a constant number of levels, and when G is a subdivision of a triconnected planar graph with bounded degree.