2026-08-07T04:28:12Z https://drops.dagstuhl.de/oai

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

Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs Büngener, Aaron Kaufmann, Michael Crossing Lemma k-planar graphs discharging method The classical Crossing Lemma by Ajtai et al. and Leighton from 1982 gave an important lower bound of cm³/n² for the number of crossings in any drawing of a given graph of n vertices and m edges. The original value was c = 1/100, which then has gradually been improved. Here, the bounds for the density of k-planar graphs played a central role. Our new insight is that for k = 2,3 the k-planar graphs have substantially fewer edges if specific local configurations that occur in drawings of k-planar graphs of maximum density are forbidden. Therefore, we are able to derive better bounds for the crossing number cr(G) of a given graph G. In particular, we achieve a bound of cr(G) ≥ 73/18m-305/18(n-2) for the range of 5n < m ≤ 6n, while our second bound cr(G) ≥ 5m - 407/18(n-2) is even stronger for larger m > 6n. For m > 6.79n, we finally apply the standard probabilistic proof from the BOOK and obtain an improved constant of c > 1/27.61 in the Crossing Lemma. Note that the previous constant was 1/29. Although this improvement is not too impressive, we consider our technique as an important new tool, which might be helpful in various other applications. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron Büngener and Michael Kaufmann 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.29 urn:nbn:de:0030-drops-213136 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.29 eng https://creativecommons.org/licenses/by/4.0/legalcode