Fast calculation of the variance of edge crossings in random arrangements

Lluís Alemany-Puig, Ramon Ferrer-i-Cancho

The crossing number of a graph $G$, $\mathrm{cr}(G)$, is the minimum number of edge crossings arising when drawing a graph on a certain surface. Determining $\mathrm{cr}(G)$ is a p…