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 Gamma(H) of a subgraph H of a directed graph G and asks whether Gamma(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.