2026-08-01T06:31:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21311 2024-10-28T09:51:05Z ddc:004 open_access

On k-Planar Graphs Without Short Cycles Bekos, Michael A. Bose, Prosenjit Büngener, Aaron Dujmović, Vida Hoffmann, Michael Kaufmann, Michael Morin, Pat Odak, Saeed Weinberger, Alexandra Beyond-planar Graphs k-planar Graphs Local Crossing Number Crossing Number Discharging Method Crossing Lemma 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 c√kn, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Bekos and Prosenjit Bose and Aaron Büngener and Vida Dujmović and Michael Hoffmann and Michael Kaufmann and Pat Morin and Saeed Odak and Alexandra Weinberger 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.27 urn:nbn:de:0030-drops-213117 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode