„Divide-and-conquer“ erweist sich als effektive Methode algorithmische und
kombinatorische Probleme in der Informatik zu lösen. Die Idee hinter diesem
Ansatz ist es, das ursprüngliche Problem in einfachere Teilprobleme zu
zergliedern, welche, nachdem sie gelöst wurden, wieder zum Ausgangsproblem
zusammengesetzt werden. Um diesen Ansatz auf planare Graphen anwenden zu können,
werden planare Separatoren benötigt, die die Graphen in mehrere Komponenten
zerlegen. Ziel der vorliegenden Arbeit ist es, verschiedene Beweise für planare
Separatoren eingehender zu untersuchen und einen Überblick über die
verschiedenen Beweise zu geben. Zu diesem Zweck werden zunächst die wichtigsten
theoretischen Begriffe vorgestellt. Aufbauend auf den theoretischen Grundlagen
werden vier ausgewählte Beweise für planare Separatoren vorgestellt. Dabei
handelt es sich um die Beweise von Lipton und Tarjan, Goodrich, Gazit und Miller
sowie Spielman und Teng. Sie werden im Detail untersucht, um sie anhand der
hieraus gewonnenen Erkenntnisse zu vergleichen und in einer Rangliste zu
bewerten. Der Beweis von Spielman und Teng überzeugt durch die kurze Darstellung
und die Verknüpfung von Graphentheorie und Geometrie. Der grundlegende Beweis
von Lipton und Tarjan belegt den zweiten Platz, weil er am einfachsten
nachzuvollziehen ist. Der Ansatz von Goodrich folgt auf Platz drei, da die
zusätzlich benötigten Datenstrukturen den Beweis komplizierter gestalten. Die
Herangehensweise von Gazit und Miller belegt den letzten Platz durch ihre
hohe Komplexität.