Graphen, die sich in die Ebene zeichnen lassen, ohne dass sich ihre Kanten schneiden, heißen planare Graphen. Sie spielen in der Informatik eine wichtige Rolle: einige algorithmische Probleme lassen sich auf planaren Graphen effizienter als auf allgemeinen lösen, wie zum Beispiel dem Finden von kürzesten Wegen oder dem Bestimmen von maximalen Flüssen. Es gibt eine Vielzahl von Algorithmen, die in linearer Zeit entscheiden, ob ein Graph planar ist und gegebenenfalls eine Einbettung in die Ebene finden. Ein grundlegender Meilenstein hierfür war der Algorithmus von Booth und Lueker, der auf einer neuen Datenstruktur namens PQ-Bäumen basiert. Es wurden immer einfachere Algorithmen vorgestellt, die einen anderen Ansatz verfolgten oder die Datenstruktur modifizierten. Diese Arbeit stellt neben den PQ-Bäumen zwei dieser Algorithmen vor: den Algorithmus von Booth und Lueker (1976), sowie einen neuen, einfacheren Algorithmus von Häupler und Tarjan (2008), der PQ-Bäume auf eine andere Weise benutzt.