Ajtai et al. [1]} and, independently, Leighton [2]} discovered
that the crossing number \(cr(G)\)  of any graph \(G\)  with \(n\)  vertices and \(m > 4n\) 
edges is at least \(cm^3/n^2\)  for some \(c>0\) . This fact is known as Crossing Lemma.
The currently best bound is \(c=1/29\) 
if \(m \ge 6.95 n\)  [3]}. In consequence, complete
graphs \(K_n\)  have \(\Omega (n^4)\)  many crossings. The Gay or Harary-Hill
conjecture states that \(cr(K_n) = \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 \) , which has been proven for \(n \le 12\) 
[4]}.
Hence, any drawing of \(K_{12}\)  has at least 150 crossings.
Similarly, there are upper and lower bounds on the
crossing numbers of complete bipartite graphs [5]},
hypercubes and cube-connected cycles, where
a lower bound is \(\frac{1}{20} 4^d - (9d+1)2^{d-1}\)  for the
\(d\) -dimensional cube-connected cycle [6]}.
