Min-$k$-planar Drawings of Graphs


  • Carla Binucci University of Perugia
  • Aaron Büngener University of Tübingen
  • Giuseppe Di Battista Roma Tre University
  • Walter Didimo University of Perugia
  • Vida Dujmović University of Ottawa
  • Seok-Hee Hong University of Sydney
  • Michael Kaufmann University of Tübingen
  • Giuseppe Liotta University of Perugia
  • Pat Morin Carleton University
  • Alessandra Tappini University of Perugia




Beyond planarity, k-planarity, edge density


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.


Download data is not yet available.




How to Cite

Binucci, C., Büngener, A., Di Battista, G., Didimo, W., Dujmović, V., Hong, S.-H., … Tappini, A. (2024). Min-$k$-planar Drawings of Graphs. Journal of Graph Algorithms and Applications, 28(2), 1–35. https://doi.org/10.7155/jgaa.v28i2.2925