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$ 上所有不交叉的單調哈密頓循環。