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∈ { 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.

Angelini, P., DA LOZZO, G., Forster, H., Schneck, T. (2020). 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.403-419). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-68766-3_32].

2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth

Angelini Patrizio;Da Lozzo Giordano;
2020

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∈ { 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.
978-3-030-68765-6
Angelini, P., DA LOZZO, G., Forster, H., Schneck, T. (2020). 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.403-419). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-68766-3_32].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/386171
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact