TY - JOUR
AU - Binucci, Carla
AU - Büngener, Aaron
AU - Di Battista, Giuseppe
AU - Didimo, Walter
AU - Dujmović, Vida
AU - Hong, Seok-Hee
AU - Kaufmann, Michael
AU - Liotta, Giuseppe
AU - Morin, Pat
AU - Tappini, Alessandra
PY - 2024/05/17
Y2 - 2024/10/05
TI - Min-$k$-planar Drawings of Graphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 2
SE -
DO - 10.7155/jgaa.v28i2.2925
UR - https://www.jgaa.info/index.php/jgaa/article/view/2925
SP - 1-35
AB - <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>
ER -