An Algorithm for Estimating the Crossing Number of Dense Graphs, and Continuous Analogs of the Crossing and Rectilinear Crossing Numbers

Abstract We present a deterministic $$n^{2+o(1)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> -time algorithm that approximates the crossing number of any graph G of order n up to an additive error of $$o(n^4)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We also provide a randomized polynomial-time algorithm that constructs a drawing of G with $$\text {cr}(G)+o(n^4)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>cr</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> crossings. These results yield a $$1+o(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.