1. On $k$-planar Graphs without Short Cycles
- Author
-
Bekos, Michael A., Bose, Prosenjit, Büngener, Aaron, Dujmović, Vida, Hoffmann, Michael, Kaufmann, Michael, Morin, Pat, Odak, Saeed, and Weinberger, Alexandra
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics - 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 $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., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
- Published
- 2024