Upward Pointset Embeddings of Planar st-Graphs
<|reference_start|>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 \subset \mathbb{R}^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, 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(n^{4k})$ time with $O(n^{3k})$ space, and to enumerate all UPSEs of $G$ on $S$ with $O(n)$ worst-case delay, using $O(k n^{4k} \log n)$ space, after $O(k n^{4k} \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(n^2)$ space, after $O(n^2)$ set-up time.<|reference_end|>
@article{alegria2024upward,
    title={Upward Pointset Embeddings of Planar st-Graphs},
    author={Carlos Alegria, Susanna Caroppo, Giordano Da Lozzo, Marco D'Elia,
  Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso, Maurizio Patrignani},
    journal={arXiv preprint arXiv:2408.17369},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.17369},
    primaryClass={cs.DS cs.CG cs.DM}
}