Upward Pointset Embeddings of Planar st-Graphs

We study upward pointset embeddings (UPSEs) of planar st-graphs. Let G be a planar st-graph and let S⊂R2 be a pointset with |S|=|V(G)|. An UPSE of G on S is an upward planar straight-line drawing of G that maps the vertices of G to the points of S. We consider both the problem of testing the existence of an UPSE of G on S (UPSE Testing) and the problem of enumerating all UPSEs of G on S. We prove that UPSE Testing is NP-complete even for st-graphs that consist of a set of directed st-paths sharing only s and t. On the other hand, if G is an n-vertex planar st-graph whose maximum st-cutset has size k, then UPSE Testing can be solved in O(n4k) time with O(n3k) space; also, all the UPSEs of G on S can be enumerated with O(n) worst-case delay, using O(kn4klogn) space, after O(kn4klogn) set-up time. Moreover, for an n-vertex st-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE on a given pointset, which can be tested in O(nlogn) time. Related to this result, we give an algorithm that, for a set S of n points, enumerates all the non-crossing monotone Hamiltonian cycles on S with O(n) worst-case delay, using O(n2) space, after O(n2) set-up time.