查看“WikiEdge:ArXiv-2409.01889v1/methods”的源代码

<div style="float: right;">[{{fullurl:WikiEdge:ArXiv-2409.01889v1/methods|action=edit}} 编辑]</div>
这篇文献的工作部分详细介绍了[[弱化层级平面图]]（[[Weakly Leveled Planar Graphs]]）的计算和组合特性。以下是这部分的主要内容：
# '''弱化层级平面图（Weakly Leveled Planar Graphs）'''：
#* 定义了弱化层级平面图的概念，即图中每个顶点表示为一系列水平线上的点，称为层级（[[Levels]]），每条边要么是水平线段，要么是严格单调的曲线。
# '''s-Span 弱化层级平面图（s-Span Weakly Leveled Planar Graphs）'''：
#* 提出了s-Span弱化层级平面图的概念，即图中每条边最多接触s+1个层级。
# '''参数化复杂性（Parameterized Complexity）'''：
#* 研究了s-Span弱化层级平面图问题的参数化复杂性，特别是针对[[顶点覆盖数]]（[[Vertex Cover Number]]）和[[树深度]]（[[Treedepth]]）的参数化算法。
# '''组合界限（Combinatorial Bounds）'''：
#* 为不同图类（如[[2-外平面图]]、[[3-连通循环树]]等）的弱化层级平面图提供了跨度的上下界。
# '''计算和组合方法（Computational and Combinatorial Approaches）'''：
#* 从计算和组合的角度探讨了如何从图中计算出s-Span弱化层级平面图，包括证明了问题的para-NP难度，以及展示了如何利用图的结构参数设计固定参数可解（[[FPT]]）算法。