Kreuzungsminimierung im automatisierten Graphenzeichnen

automatisierten Graphenzeichnen. Der Kern meiner Arbeit ist das
Constrained Crossing Minimization Problem, das eine wichtige
Teilaufgabe in der Planarisierungsmethode zum Zeichnen nichtplanarer
Graphen darstellt.

Ich untersuche erstmals die Komplexität des Problems und stelle
interessante Eigenschaften optimaler Lösungen vor. Weiterhin
entwickle ich einen Lösungsansatz, der Instanzen bis zu einer
gewissen Grössenordnung beweisbar optimal lösen kann, und verbesserte
Heuristiken für grössere Probleme. Die verschiedenen Methoden werden
in einem umfangreichen experimentellen Teil an einer Menge von
Benchmark-Graphen überprüft.