ein Algorithmus, der für einen gegebenen Graphen G eine kreuzungsfreie Einbettung dieses Graphen in einen bestimmten topologischen Raum erzeugt, falls eine solche existiert. Manchmal werden auch Algorithmen so genannt, die lediglich testen, ob eine derartige Einbettung existiert, ohne sie anzugeben.

Eine Vielzahl effizienter Einbettungsalgorithmen wurde für spezielle topologische Räume entwickelt.

Hopcroft und Tarjan gaben 1974 den ersten Planaritätstest mit linearer Laufzeit an, d. h. einen Algorithmus, der testet, ob ein gegebener Graph ein planarer Graph ist.

Zwei Jahre später wurde ein Algorithmus entwickelt, der in ebenfalls linearer Laufzeit tatsächlich eine kreuzungsfreie Einbettung eines gegebenen Graphen in die Ebene konstruiert, falls eine solche existiert.

Im Jahre 1999 gab Mohar einen Einbettungsalgorithmus mit linearer Laufzeit für orientierbare oder nicht-orientierbare Fläche beliebigen festen Geschlechts an. Er verwendete hierfür einen Einbettungsalgorithmus mit linearer Laufzeit für die projektive Ebene, d. h. die nicht-orientierbare Fläche N₁ vom Geschlecht Eins, und einen ebensolchen Algorithmus für den Torus, d. h. die orientierbare Fläche S₁ vom Geschlecht Eins, von Juvan, Marincek und Mohar (1995).

Es ist i. allg. ein NP-vollständiges Problem, für einen gegebenen Graphen G und eine gegebene natürliche Zahl k zu entscheiden, ob das Geschlecht von G die Zahl k nicht überschreitet. Filotti, Miller und Reif gaben 1979 einen Algorithmus an, der das Geschlecht h eines Graphen mit n Ecken in einer Laufzeit von O(n^O(h)) bestimmt.