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）算法。