minimale Anzahl von Kreuzungen in einer normalen Einbettung eines Graphen in die Ebene ℝ².

Da jeder Graph eine solche Einbettung besitzt, ist die Kreuzungszahl wohldefiniert. Oft sind für die Kreuzungszahl spezieller Graphen nur obere Schranken bekannt, die durch Angabe einer konkreten Einbettung bewiesen werden.

Die Kreuzungszahl des vollständigen Graphen K_n beträgt so höchstens \begin{eqnarray}\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,\end{eqnarray}

und die Kreuzungszahl des vollständigen bipartiten Graphen K_n,m beträgt höchstens \begin{eqnarray}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor.\end{eqnarray}

Die Frage nach dem genauen Wert der Kreuzungszahl des vollständigen bipartiten Graphen ist als „Turán’s brick-factory problem“ bekannt.

Die oben angegebene Schranke wurde 1954 von K.Zarankiewicz bewiesen.