Eine oft verwendete Strategie zum Entwurf effizienter Algorithmen ist ,,divide-and-conquer``. Dabei wird das betrachtete Problem in zwei (oder mehr) kleinere Teilprobleme zerlegt, die dann rekursiv mit dieser Methode gelöst werden. Die Lösungen der Teilprobleme werden zu einer Lösung des Ausgangsproblems zusammengefügt.

Damit ,,divide-and-conquer`` sinnvoll angewendet werden kann, muß folgendes erfüllt sein: - Die Teilprobleme müssen von gleicher Natur wie das Ausgangsproblem und bzgl. der Problemstellung voneinander unabhängig sein. - Die Teilprobleme müssen signifikant kleiner als das Ausgangsproblem sein. - Der Aufwand zum Finden einer Lösung aus den Lösungen der Teilprobleme muß vergleichsweise gering sein.

Soll ,,divide-and-conquer`` auf Graphenprobleme angewendet werden, so bieten Separatoren eine Möglichkeit, das Ausgangsproblem in unabhängige Teilprobleme zu zerlegen. Sei K eine unter Untergraphenbildung abgeschlossene Graphenklasse (d.h., falls G_1 in K und G_2 Untergraph von G_1 ist, so gilt auch G_2 in K). Die Graphenklasse K erfüllt ein f(n)-Separatortheorem, falls Konstanten a<1 und b>0 existieren, so daß die Knoten jedes Graphen G in K in drei disjunkte Mengen A, B und S so zerlegt werden können, daß keine Kanten Knoten aus A mit Knoten aus B verbinden und weder A noch B mehr als a*n Knoten haben, weiterhin soll die Größe von S durch b*f(n) beschränkt sein. Läßt sich solch eine Zerlegung für alle Graphen G in K schnell finden, so lassen sich für diese Graphen viele Probleme mit ,,divide-and-conquer`` lösen. Der Aufwand zum Zusammenfügen der Teillösungen ist i.a. eine Funktion g(f(n)), so daß f(n) möglichst klein, d.h. zumindest f(n) in o(n), sein sollte.

Lipton & Tarjan stellten 1977 ihr n^(1/2)-Separatortheorem für planare Graphen vor. Bis dahin waren praktikable Separatortheoreme nur für recht spezielle Graphenklassen bekannt, wie z.B. ein 1-Separatortheorem für Bäume (mit a=2/3) und für Gittergraphen ein n^(1/2)-Separatortheorem (ebenfalls mit a=2/3). Planare Graphen hingegen tauchen in vielen praktischen Problemen auf und so sollen hier die Separatortheoreme von Lipton & Tarjan vorgestellt und einige Anwendungen dieser Theoreme dargestellt werden. Die Effizienz dieser Algorithmen soll schließlich noch mit der anderer Algorithmen, die ohne Separatoren arbeiten, verglichen werden.