Name
Abstract | ||
|---|---|---|
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$. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-68766-3_32 | GD |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrizio Angelini | 1 | 0 | 0.34 |
| Giordano Da Lozzo | 2 | 0 | 0.68 |
| Henry Förster | 3 | 3 | 4.40 |
| Thomas Schneck | 4 | 0 | 0.34 |