WikiEdge:ArXiv-2408.17369v1/abs

[{fullurl:WikiEdge:ArXiv-http://arxiv.org/abs/2408.17369v1/abs%7Caction=edit} 编辑]

• 标题：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$ 上所有不交叉的单调哈密顿循环。