Answers are grounded in this paper and cite their sources.
Study improves crossing number bounds in dense k-planar graphs, indicating new analytical tools.
The classical Crossing Lemma by Ajtai et al.~and Leighton from 1982 gave an important lower bound of c m³/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) ≥ 37/9m-155/9(n-2) for the range of 5n < m ≤ 6n, while our second bound cr(G) ≥ 5m - 203/9(n-2) is even stronger for larger $m>6n$. For $m > 6.77n$, we finally apply the standard probabilistic proof from the BOOK and obtain an improved constant of $c>1/27.48$ 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.
No takes yet. Share an insight, caveat, or question.
Büngener et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: