On k-planar Graphs without Short Cycles

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 5). For all three settings and all k\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 c\, n, for some explicit constant c that depends on k and on the setting. For general k 4 our bounds are of the form ckn, 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.