On $k$-planar Graphs without Short Cycles
<|reference_start|>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 $\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 $c\,n$, for some explicit constant $c$ that depends on $k$ and on the setting. For general $k \geq 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.<|reference_end|>
@article{bekos2024on,
    title={On $k$-planar Graphs without Short Cycles},
    author={Michael A. Bekos, Prosenjit Bose, Aaron B"ungener, Vida Dujmovi'c,
  Michael Hoffmann, Michael Kaufmann, Pat Morin, Saeed Odak, Alexandra
  Weinberger},
    journal={arXiv preprint arXiv:2408.16085},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.16085},
    primaryClass={math.CO cs.DM}
}