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

<div style="float: right;">[{{fullurl:WikiEdge:ArXiv-2409.01889v1/summary|action=edit}} 编辑]</div>
本文研究了[[平面图]]的弱分层平面图，其中每个顶点表示为沿水平线序列（称为层级）的点，每条边要么是水平线段，要么是严格单调的曲线。如果一个图允许这样的绘制，其中边的跨度至多为s，则称该图为s-跨度弱分层平面图。我们从计算和组合的角度探讨了计算s-跨度弱分层平面图的问题。我们证明了这个问题相对于其自然参数s是[[para-NP]]难的，并研究了其相对于广泛使用的结构参数的复杂性。我们展示了关于[[顶点覆盖]]数的多项式大小的核的存在，并证明了当以[[树深度]]为参数时，该问题是FPT。我们还为各种图类提供了跨度的上下界。值得注意的是，我们展示了[[循环树]]，一种2-外平面图的家族，概括了[[Halin图]]，是Θ(log n)-跨度弱分层平面图，并且当3-连通时是4-跨度弱分层平面图。作为这些组合结果的副产品，我们得到了所考虑的图族的边长比的改进界限。