Geodesic
Min-$k$-planar Drawings of Graphs
Carla Binucci1 ; Aaron Büngener2 ; Giuseppe Di Battista3 ; Walter Didimo1 ; Vida Dujmović4 ; Seok-Hee Hong5 ; Michael Kaufmann2 ; Giuseppe Liotta1 ; Pat Morin6 ; Alessandra Tappini1
1 University of Perugia
2 University of Tübingen
3 Roma Tre University
4 University of Ottawa
5 University of Sydney
6 Carleton University
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023 , Tome 28 (2024) no. 2, pp. 1-35.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the $k$-planar drawings $(k \geq 1)$, where each edge cannot cross more than $k$ times. We generalize $k$-planar drawings, by introducing the new family of min-$k$-planar drawings. In a min-$k$-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than $k$ crossings. We prove a general upper bound on the number of edges of min-$k$-planar drawings, a finer upper bound for $k=3$, and tight upper bounds for $k=1,2$. Also, we study the inclusion relations between min-$k$-planar graphs (i.e., graphs admitting min-$k$-planar drawings) and $k$-planar graphs.In our setting, we only allow simple drawings, that is, any two edges cross at most once, no two adjacent edges cross, and no three edges intersect at a common point.
DOI : 10.7155/jgaa.v28i2.2925
Keywords: Beyond planarity, k-planarity, edge density

Carla Binucci 1 ; Aaron Büngener 2 ; Giuseppe Di Battista 3 ; Walter Didimo 1 ; Vida Dujmović 4 ; Seok-Hee Hong 5 ; Michael Kaufmann 2 ; Giuseppe Liotta 1 ; Pat Morin 6 ; Alessandra Tappini 1

1 University of Perugia
2 University of Tübingen
3 Roma Tre University
4 University of Ottawa
5 University of Sydney
6 Carleton University 
@article{JGAA_2024_28_2_a1,
     author = {Carla Binucci and Aaron B\"ungener and Giuseppe Di Battista and Walter Didimo and Vida Dujmovi\'c and Seok-Hee Hong and Michael Kaufmann and Giuseppe Liotta and Pat Morin and Alessandra Tappini},
     title = {Min-$k$-planar {Drawings} of {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1--35},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2024},
     doi = {10.7155/jgaa.v28i2.2925},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2925/}
}
TY  - JOUR
AU  - Carla Binucci
AU  - Aaron Büngener
AU  - Giuseppe Di Battista
AU  - Walter Didimo
AU  - Vida Dujmović
AU  - Seok-Hee Hong
AU  - Michael Kaufmann
AU  - Giuseppe Liotta
AU  - Pat Morin
AU  - Alessandra Tappini
TI  - Min-$k$-planar Drawings of Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 1
EP  - 35
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2925/
DO  - 10.7155/jgaa.v28i2.2925
LA  - en
ID  - JGAA_2024_28_2_a1
ER  - 
%0 Journal Article
%A Carla Binucci
%A Aaron Büngener
%A Giuseppe Di Battista
%A Walter Didimo
%A Vida Dujmović
%A Seok-Hee Hong
%A Michael Kaufmann
%A Giuseppe Liotta
%A Pat Morin
%A Alessandra Tappini
%T Min-$k$-planar Drawings of Graphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 1-35
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2925/
%R 10.7155/jgaa.v28i2.2925
%G en
%F JGAA_2024_28_2_a1
Carla Binucci; Aaron Büngener; Giuseppe Di Battista; Walter Didimo; Vida Dujmović; Seok-Hee Hong; Michael Kaufmann; Giuseppe Liotta; Pat Morin; Alessandra Tappini. Min-$k$-planar Drawings of Graphs. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023
					, Tome 28 (2024) no. 2, pp. 1-35. doi : 10.7155/jgaa.v28i2.2925. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2925/

Cité par Sources :