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, for n-vertex planar st-graphs whose maximum st-cutset has size k, we prove that it is possible to solve UPSE Testing in O(n4k) time with O(n3k) space, and to enumerate all UPSEs of G on S with O(n) worst-case delay, using O(kn4k log n) space, after O(kn4k log n) 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 poinset, which can be tested in O(n log n) 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.