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

<div style="float: right;">[{{fullurl:WikiEdge:ArXiv-2409.01889v1/abs|action=edit}} 编辑]</div>
* '''标题'''：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$-跨度弱层次平面图。作为这些组合结果的副产品，我们获得了所考虑图类的边长比的改进界限。