Ein klassisches Problem der Graphentheorie ist die Bestimmung einer
minimalen Teilmenge 
der Knotenmenge,
so da\3 jede Kante des Graphen
zu mindestens einem der Knoten dieser Teilmenge inzident ist.
Da dieses Problem 
-hart ist, greift man auf
Approximationsalgorithmen zurück. Es gibt sehr einfache Algorithmen,
die Überdeckenden Knotenmengen finden, die höchstens doppelt so
gro\3 wie die minimale Überdeckende Knotenmenge sind.
Bis heute ist für allgemeine Graphen auch kein wesentlich besseres
Ergebnis bekannt.
Für planare Graphen sieht dies anders aus. In [11] wird
zunächst ein Algorithmus vorgestellt, der im allgemeinen ebenfalls
eine 2-Approximation liefert, auf planaren Graphen jedoch eine Güte
von 
garantiert. Seine Laufzeit ist linear.
Die Situation ist jedoch noch viel besser. Es gibt ein sogenanntes
Approximationsschema, d.h. eine Familie von Algorithmen, so da\3
es für jedes 
einen Approximationsalgorithmus gibt,
der eine Lösung produziert, die nicht weiter als um einen Faktor
von der optimalen Lösung entfernt ist.
Dieses Schema wird aus einem bekannten Schema für das Problem
der maximalen unabhängigen Knotenmengen (siehe früherer Vortrag)
konstruiert.