Die maximale Teilmenge der Knotenmenge eines Graphen zu berechnen,
so da\3 es zwischen diesen Knoten keine Kante gibt, ist ein
-hartes Problem. Für allgemeine Graphen gibt es unter der
Annahme 
nicht einmal einen
Approximationsalgorithmus mit konstantem Approximationsfaktor.
Für planarer Graphen ergibt sich ein solcher Approximationsalgorithmus
dagegen sofort aus der 4-Färbbarkeit.
In [7] wird jedoch ein qualitativ wesentlich besserer Algorithmus
vorgestellt: er liefert in Zeit 
eine unabhängige
Knotenmenge, die mindestens halb so gro\3 ist wie eine maximale
unabhängige Knotenmenge.
Es geht jedoch noch besser. Auf planaren Graphen gibt es sogar ein
sogenanntes Approximationsschema, d.h. eine Familie von Algorithmen, so
da\3 es für jedes 
einen Algorithmus gibt, der eine
maximale unabhängige Knotenmenge bis auf den Faktor 
approximiert.
Nach einer kurzen Einführung des Begriff des Approximationsschemas
soll ein solches kurz vorgestellt werden.