WikiEdge:ArXiv-2409.01889v1/abs

编辑

• 标题：Weakly Leveled Planarity with Bounded Span
• 中文标题：弱层次平面性与有界跨度
• 发布日期：2024-09-03T13:28:41+00:00
• 作者：Michael Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, Ioannis G. Tollis
• 分类：cs.CG, cs.DS
• 原文链接：http://arxiv.org/abs/2409.01889v1

摘要：本文研究了图的平面绘制，其中每个顶点被表示为一系列水平线上的一个点，称为层次，每条边要么是水平线段，要么是严格的 $y$ 单调曲线。如果一个图允许这样的绘制，并且边的跨度最多为 $s$，则称该图为 $s$-跨度弱层次平面图；边的跨度是它所接触的层数减去一。我们从计算和组合的角度研究计算 $s$-跨度弱层次平面绘制的问题。我们证明该问题在其自然参数 $s$ 下是 para-NP-hard，并研究其在广泛使用的结构参数下的复杂性。我们展示了关于顶点覆盖数的多项式大小核的存在，并证明该问题在树深度参数化下是 FPT。我们还为各种图类提供了跨度的上下界。值得注意的是，我们展示了循环树，这是一类推广 Halin 图的 $2$-外平面图，是 $\Theta(\log n)$-跨度弱层次平面图，并且在 $3$-连通时是 $4$-跨度弱层次平面图。作为这些组合结果的副产品，我们获得了所考虑图类的边长比的改进界限。