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
Computer science, Discrete mathematics, Data structures and algorithms, Computational geometry
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.