The minimal crossing number of a graph.
A drawing of a graph $G$ is a drawing in $\mathbb{R}^2$ such that

• the vertices of $G$ are distinct points,
• the edges of $G$ are simple curves joining their endpoints,
• no edge passes through a vertex, and
• no three edges cross in a common point.

The minimal crossing number of $G$ is then the minimal number of crossings of edges in a drawing of $G$.
In particular, a graph is planar if and only if its minimal crossing number is $0$.
It is moreover conjectured that the crossing number of the complete graph $K_n$ [1] is
$$\frac{1}{4}\lfloor \frac{n}{2} \rfloor\lfloor \frac{n-1}{2} \rfloor\lfloor \frac{n-2}{2} \rfloor\lfloor \frac{n-3}{2} \rfloor,$$
and the crossing number of the complete bipartite graph $K_{n,m}$ [2] is
$$\lfloor \frac{n}{2} \rfloor\lfloor \frac{n-1}{2} \rfloor\lfloor \frac{m}{2} \rfloor\lfloor \frac{m-1}{2} \rfloor.$$
A general algorithm to compute the crossing number is e.g. given in [3].
This statistics data was provided by Markus Chimani [6].

[1] Guy, R. K., Jenkyns, T., Schaer, J. The toroidal crossing number of the complete graph MathSciNet:0220630
[2] Zarankiewicz, K. On a problem of P. Turan concerning graphs MathSciNet:0063641
[3] Hliněný, P., Derňár, M. Crossing Number is Hard for Kernelization arXiv:1512.02379
[4] wikipedia:Crossing_number_(graph_theory)
[5] http://mathworld.wolfram.com/GraphCrossingNumber.html
[6] http://www-lehre.inf.uos.de/theoinf/lib/exe/fetch.php/pubs/computingcrossingnumbers_phdthesis_chimani_pdf.pdf

Dec 09, 2015 at 12:27 by Christian Stump

Dec 30, 2016 at 10:35 by Christian Stump