@article{Binucci_Büngener_Di Battista_Didimo_Dujmović_Hong_Kaufmann_Liotta_Morin_Tappini_2024, title={Min-$k$-planar Drawings of Graphs}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2925}, DOI={10.7155/jgaa.v28i2.2925}, abstractNote={<p>The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as <em>beyond-planar graph drawing</em>. One of the most studied types of drawings in this area are the <em>$k$-planar drawings</em> $(k \geq 1)$, where each edge cannot cross more than $k$ times. We generalize $k$-planar drawings, by introducing the new family of <em>min-$k$-planar drawings.</em> 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.<br />In our setting, we only allow <em>simple</em> drawings, that is, any two edges cross at most once, no two adjacent edges cross, and no three edges intersect at a common point.</p>}, number={2}, journal={Journal of Graph Algorithms and Applications}, author={Binucci, Carla and Büngener, Aaron and Di Battista, Giuseppe and Didimo, Walter and Dujmović, Vida and Hong, Seok-Hee and Kaufmann, Michael and Liotta, Giuseppe and Morin, Pat and Tappini, Alessandra}, year={2024}, month={May}, pages={1–35} }