查看“WikiEdge:ArXiv-2408.17369v1/abs”的源代码

<!-- 不要移除下面第一行，如果有编辑错误，请直接修改第二行以后的内容 -->
<div style="float: right;">[{fullurl:WikiEdge:ArXiv-http://arxiv.org/abs/2408.17369v1/abs|action=edit} 编辑]</div>
* '''标题'''：Upward Pointset Embeddings of Planar st-Graphs
* '''中文标题'''：平面 st-图的向上点集嵌入
* '''发布日期'''：2024-08-30T15:58:23+00:00
* '''作者'''：Carlos Alegria, Susanna Caroppo, Giordano Da Lozzo, Marco D'Elia, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso, Maurizio Patrignani
* '''分类'''：cs.DS, cs.CG, cs.DM
*'''原文链接'''：http://arxiv.org/abs/2408.17369v1
'''摘要'''：我们研究了平面 $st$-图的[[向上点集嵌入]]（UPSE）。设 $G$ 为一个平面 $st$-图，$S \subset \mathbb{R}^2$ 为一个[[点集]]，且 $|S|=|V(G)|$。$G$ 在 $S$ 上的 UPSE 是 $G$ 的一个向上平面直线图，它将 $G$ 的顶点映射到 $S$ 的点上。我们考虑了测试 $G$ 在 $S$ 上是否存在 UPSE（UPSE 测试）的问题以及枚举 $G$ 在 $S$ 上所有 UPSE 的问题。我们证明了即使对于仅由共享 $s$ 和 $t$ 的一组有向 $st$-路径组成的 $st$-图，UPSE 测试也是 [[NP 完全]]的。另一方面，对于最大 $st$-割集大小为 $k$ 的 $n$ 顶点平面 $st$-图，我们证明了可以在 $O(n^{4k})$ 时间和 $O(n^{3k})$ 空间内解决 UPSE 测试，并在 $O(k n^{4k} \log n)$ 的设置时间后，使用 $O(k n^{4k} \log n)$ 空间，以 $O(n)$ 的最坏情况延迟枚举 $G$ 在 $S$ 上的所有 UPSE。此外，对于底层图为一个[[循环 (图论)|循环]]的 $n$ 顶点 $st$-图，我们提供了一个在给定点集上存在 UPSE 的充要条件，该条件可以在 $O(n \log n)$ 时间内测试。与此结果相关，我们给出了一个算法，对于一个包含 $n$ 个点的集合 $S$，在 $O(n^2)$ 的设置时间后，使用 $O(n^2)$ 空间，以 $O(n)$ 的最坏情况延迟枚举 $S$ 上所有不交叉的[[单调哈密顿循环]]。