WikiEdge:ArXiv-2409.01889v1/methods

編輯

這篇文獻的工作部分詳細介紹了弱化層級平面圖（Weakly Leveled Planar Graphs）的計算和組合特性。以下是這部分的主要內容：

1. 弱化層級平面圖（Weakly Leveled Planar Graphs）：
   • 定義了弱化層級平面圖的概念，即圖中每個頂點表示為一系列水平線上的點，稱為層級（Levels），每條邊要麼是水平線段，要麼是嚴格單調的曲線。
2. s-Span 弱化層級平面圖（s-Span Weakly Leveled Planar Graphs）：
   • 提出了s-Span弱化層級平面圖的概念，即圖中每條邊最多接觸s+1個層級。
3. 參數化複雜性（Parameterized Complexity）：
   • 研究了s-Span弱化層級平面圖問題的參數化複雜性，特別是針對頂點覆蓋數（Vertex Cover Number）和樹深度（Treedepth）的參數化算法。
4. 組合界限（Combinatorial Bounds）：
   • 為不同圖類（如2-外平面圖、3-連通循環樹等）的弱化層級平面圖提供了跨度的上下界。
5. 計算和組合方法（Computational and Combinatorial Approaches）：
   • 從計算和組合的角度探討了如何從圖中計算出s-Span弱化層級平面圖，包括證明了問題的para-NP難度，以及展示了如何利用圖的結構參數設計固定參數可解（FPT）算法。