Es gibt zwei klassische Verfahren, um in linearer Zeit zu entscheiden, on ein Graph planar ist. Dies ist zum einen der ``path addition'' Algorithmus von Hopcoft und Tarjan und zum anderen der ``vertex addition'' Algorithmus, der auf Lempel, Even und Cederbaum zurückgeht. Zu jedem der beiden Ansätze wurden auch Verfahren entwickelt, die im Falle der Planarität eine planare Einbettung berechnen bzw. im umgekehrten Falle einen Kuratowski-Teilgraphen als Beweis für die Nicht-Planarität ermitteln.
Im Seminar soll der ``vertex addition'' Algorithmus ausführlich besprochen werden. Eine sehr gute Beschreibung, die das Prinzip und die Korrektheit des Verfahrens erklärt, findet sich in [1]. Ein wesentlicher Punkt ist hierbei die Betrachtung der Knoten in einer durch eine sogenannte st-Nummerierung gegebenen Reihenfolge. In [2] wird genauer auf Implementierungsdetails eingegangen und auch die Berechnung einer planaren Einbettung beschrieben (siehe auch [4]). Schlie\3lich wird in [3] eine Erweiterung des Algorithms zur ggf. erforderlichen Bestimmung eines Kuratowski-Untergraphen dargestellt. Wichtig für eine Realisierung in linearer Zeit ist die Datenstrukur der sogenannten PQ-Bäume und die effiziente Berechnung einer st-Nummerierung.