Loading...
2-Layer k-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth
Angelini, Patrizio
Da Lozzo, Giordano Förster, Henry Schneck, Thomas
Da Lozzo, Giordano
Förster, Henry
Schneck, Thomas
Citations
Altmetric:
Abstract
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 ∈ {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.
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 ∈ {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.
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 ∈ {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.
Description
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
2-layer graph drawing, k-planar graphs, Density, Crossing lemma, Pathwidth, Quasiplanar graphs
Citation
Patrizio Angelini, Giordano Da Lozzo, Henry Förster, Thomas Schneck, 2-Layer k-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth, The Computer Journal, Volume 67, Issue 3, March 2024, Pages 1005–1016.