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].

The line graph of a graph.
Let $G$ be a graph with edge set $E$. Then its line graph is the graph with vertex set $E$, such that two vertices $e$ and $f$ are adjacent if and only if they are incident to a common vertex in $G$.

The dual of the 3-connected planar components of a graph.
Replace each connected component which is 3-connected and planar with its planar dual.