WikiEdge:ArXiv-2409.01889v1/summary

编辑

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