Abstract We present a deterministic $$n^{2+o(1)}$$ 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)$$ o ( n 4 ) . We also provide a randomized polynomial-time algorithm that constructs a drawing of G with $$\text {cr}(G)+o(n^4)$$ cr ( G ) + o ( n 4 ) crossings. These results yield a $$1+o(1)$$ 1 + o ( 1 ) approximation algorithm for the crossing number of dense graphs. Our work complements a paper of Fox, Pach and Súk [20], who obtained similar results for the rectilinear crossing number. The results in [20] 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 crossing density and the rectilinear crossing density , and we prove that, in a precise sense, these are the correct continuous analogs of the crossing and rectilinear crossing numbers of graphs.

Abstract Determining whether there exists a graph such that its crossing number and pair crossing number are distinct is an important open problem in geometric graph theory. We show that $$\textit{cr}(G)=O(\mathop {\textrm{pcr}}(G)^{3/2})$$ cr ( G ) = O ( pcr ( G ) 3 / 2 ) for every graph G, improving the previous best bound by a logarithmic factor. Answering a question of Pach and Tóth, we prove that the bisection width (and, in fact, the cutwidth as well) of a graph G with degree sequence $$d_1,d_2,\dots ,d_n$$ d 1 , d 2 , ⋯ , d n satisfies $$\mathop {\textrm{bw}}(G)=O\big (\sqrt{\mathop {\textrm{pcr}}(G)+\sum _{k=1}^n d_k^2}\big )$$ bw ( G ) = O ( pcr ( G ) + ∑ k = 1 n d k 2 ) . Then we show that there is a constant $$C\ge 1$$ C ≥ 1 such that the following holds: For any graph G of order n and any set S of at least $$n^C$$ n C points in general position on the plane, G admits a straight-line drawing which maps the vertices to points of S and has no more than $$O\left( \log n\cdot \left( \mathop {\textrm{pcr}}(G)+\sum _{k=1}^n d_k^2\right) \right) $$ O log n · pcr ( G ) + ∑ k = 1 n d k 2 crossings. Our proofs rely on a slightly modified version of a separator theorem for string graphs by Lee, which might be of independent interest.

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 yield a $1+o(1)$ approximation algorithm for the crossing number of dense graphs. Our work complements a paper of Fox, Pach and Súk, who obtained similar results for the rectilinear crossing number. The results of Fox, Pach and Súk 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 we prove that, in a precise sense, these are the correct continuous analogs of the crossing and rectilinear crossing numbers of graphs.