Search

The |$2$| -layer drawing model is a well-established paradigm to visualize bipartite graphs where vertices of the two parts lie on two horizontal lines and edges lie between these lines. 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$| while there are also |$2$| -layer |$k$| -planar graphs with pathwidth at least |$(k+3)/2$|⁠. [ABSTRACT FROM AUTHOR]