Extending upward planar graph drawings

In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes as input an upward planar drawing Γ H of a subgraph H of a directed graph G and asks whether Γ H can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the Upward Planarity Extension problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the Upward Planarity Extension problem can be solved in O ( n log ⁡ n ) time if G is an n-vertex upward planar st-graph. This result improves upon a known O ( n 2 ) -time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the Upward Planarity Extension problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in Γ H .