das minimale Geschlecht h einer orientierbaren Fläche S_h derart, daß der Graph eine kreuzungsfreie Einbettung in S_h besitzt (Einbettung eines Graphen).

Das Geschlecht des vollständigen Graphen K_n beträgt \begin{eqnarray}\lceil (n-3)(n-4)/12\rceil \end{eqnarray} für n ≥ 3, und das Geschlecht des vollständig bipartiten Graphen K_{n, m} ist \begin{eqnarray}\lceil (n-2)(m-2)/4\rceil \end{eqnarray} für n, m ≥ 2.

Die Bestimmung des Geschlechts eines Graphen ist ein NP-schweres Problem.