On $k$-planar Graphs without Short Cycles

Abstract

We study the impact of forbidding short cycles to the edge density of $k$-planar graphs; a $k$-planar graph is one that can be drawn in the plane with at most $k$ crossings per edge. Specifically, we consider three settings, according to which the forbidden substructures are $3$-cycles, $4$-cycles or both of them (i.e., girth $\ge 5$). For all three settings and all $k\in \{1,2,3\}$, we present lower and upper bounds on the maximum number of edges in any $k$-planar graph on $n$ vertices. Our bounds are of the form $cn$, for some explicit constant $c$ that depends on $k$ and on the setting. For general $k\ge 4$ our bounds are of the form $c\sqrt{k}n$, for some explicit constant $c$. These results are obtained by leveraging different techniques, such as the discharging method, the recently introduced density formula for non-planar graphs, and new upper bounds for the crossing number of $2$-- and $3$-planar graphs in combination with corresponding lower bounds based on the Crossing Lemma.

Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)