2024/08/30 by Alegria, Carlos, Caroppo, Susanna, Da Lozzo, Giordano +5 · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2408.17369
We study upward pointset embeddings (UPSEs) of planar st-graphs. Let G be a planar st-graph and let S ⊂ ℝ2 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(k n4k log n) space, after O(k n4k 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 pointset, 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.