论文标题
$ 2 $ -LAYER $ K $ -PLANAR图：密度，交叉引理，关系和路径宽
$2$-Layer $k$-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth
论文作者
论文摘要
$ 2 $ - 层绘图模型是一个可视化二分图的范式。在此模型下，已经研究了几个平面图类别。但是，令人惊讶的是，在这种情况下，仅考虑$ k = 1 $的$ k $ - 平面图的基本类别。我们提供了一些贡献，可以解决文献中的这一差距。首先，我们显示$ 2 $ -LAYER $ K $ -PLANAR图的$ K \ in \ in \ {2,3,4,5 \} $的$ 2 $ -LAYER $ K $ -PLANAR图的紧密密度界限。基于这些结果，我们为$ 2 $ layer $ k $ -planar图提供了一个交叉引理，这意味着通用密度限制为$ 2 $ -LAYER $ K $ -PLANAR图。我们证明，对于相应的下限结构，这一义务几乎是最佳的。最后，我们研究了$ k $ - planarity和$ h $ quasiplanarity在$ 2 $ -Layer型号中的关系，并表明$ 2 $ -LAYER $ K $ -PLANAR图最多具有$ K+1 $的路径。
The $2$-layer drawing model is a well-established paradigm to visualize bipartite graphs. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of $k$-planar graphs has been considered only for $k=1$ in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of $2$-layer $k$-planar graphs with $k\in\{2,3,4,5\}$. Based on these results, we provide a Crossing Lemma for $2$-layer $k$-planar graphs, which then implies a general density bound for $2$-layer $k$-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between $k$-planarity and $h$-quasiplanarity in the $2$-layer model and show that $2$-layer $k$-planar graphs have pathwidth at most $k+1$.
