WikiEdge:ArXiv-2409.01889v1/abs

編輯

• 標題：Weakly Leveled Planarity with Bounded Span
• 中文標題：弱層次平面性與有界跨度
• 發布日期：2024-09-03T13:28:41+00:00
• 作者：Michael Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, Ioannis G. Tollis
• 分類：cs.CG, cs.DS
• 原文連結：http://arxiv.org/abs/2409.01889v1

摘要：本文研究了圖的平面繪製，其中每個頂點被表示為一系列水平線上的一個點，稱為層次，每條邊要麼是水平線段，要麼是嚴格的 $y$ 單調曲線。如果一個圖允許這樣的繪製，並且邊的跨度最多為 $s$，則稱該圖為 $s$-跨度弱層次平面圖；邊的跨度是它所接觸的層數減去一。我們從計算和組合的角度研究計算 $s$-跨度弱層次平面繪製的問題。我們證明該問題在其自然參數 $s$ 下是 para-NP-hard，並研究其在廣泛使用的結構參數下的複雜性。我們展示了關於頂點覆蓋數的多項式大小核的存在，並證明該問題在樹深度參數化下是 FPT。我們還為各種圖類提供了跨度的上下界。值得注意的是，我們展示了循環樹，這是一類推廣 Halin 圖的 $2$-外平面圖，是 $\Theta(\log n)$-跨度弱層次平面圖，並且在 $3$-連通時是 $4$-跨度弱層次平面圖。作為這些組合結果的副產品，我們獲得了所考慮圖類的邊長比的改進界限。