Optimieren über alle kombinatorischen Einbettungen eines planaren Graphen

Zusammenfassung

Nach einer kurzen Übersicht über das Graduiertenkolleg „Effizienz und Komplexität von Algorithmen und Rechenanlagen“ an der Universität des Saarlandes, welches die in diesem Papier vorgestellte Forschung mit finanziert hat, betrachten wir das Problem über alle kombinatorische Einbettungen eines planaren Graphen zu optimieren. Die Motivation für die Untersuchung dieses Problems kommt aus dem Gebiet des automatischen Zeichnens von Graphen, wo die gewählte Einbettung für die Zeichnung eines Graphen einen großen Einfluß auf die ästhetischen Eigenschaften der produzierten Zeichnung hat. Wir charakterisieren die Menge aller kombinatorischen Einbettungen eines planaren zwei-zusammenhängenden Graphen durch ein System von linearen Ungleichungen. Dieses System von linearen Ungleichungen kann mit Hilfe von SPQR-Bäumen und einer neuen Split-Operation rekursiv konstruiert werden. Wir haben unsere Methode in Experimenten auf zwei verschiedene Serien von Testgraphen angewendet und erhielten dabei überraschende Resultate: Obwohl die Anzahl der kombinatorischen Einbettungen eines planaren Graphen exponentiell in der Größe des Graphen wächst, wächst die Anzahl der bei unserer Methode verwendeten Ungleichungen und Variablen nur linear. Für alle getesteten Graphen (mit bis zu 500 Knoten) konnte das System von Ungleichungen in weniger als 6 Minuten berechnet werden.

Teilweise unterstützt durch das DFG-Projekt Mu 1129/3-1, Forschungsschwerpunkt „Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen“

Unterstützt durch das Graduiertenkolleg „Effizienz und Komplexität von Algorithmen und Rechenanlagen“