An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers

Oriol Solé Pi

Published 2024-01-01Version 1

We present a deterministic $n^{2+o(1)}$-time algorithm that approximates the crossing number of any graph $G$ of order $n$ up to an additive error of $o(n^4)$. We also provide a randomized polynomial-time algorithm that constructs a drawing of $G$ with $\text{cr}(G)+o(n^4)$ crossings. These results are made interesting by the well known fact that every dense $n$-vertex graph has crossing number $\Theta(n^4)$. Our work builds on a technique developed by Fox, Pach and S\'uk, who obtained very similar results for the rectilinear crossing number. The results by the aforementioned authors and in this paper imply that the (normalized) crossing and rectilinear crossing numbers are estimable parameters. Motivated by this, we introduce two graphon parameters, the \textit{crossing density} and the \textit{rectilinear crossing density}, and then we prove that, in a precise sense, these are the correct continuous analogs of the crossing and rectilinear crossing numbers of graphs.