Masterarbeit

Algorithmische Lösungen zur Maximierung der minimalen Kreuzungswinkel von Graphzeichnungen

Verfasser/in:
Matthias Zoche
Betreuer/in:
Philipp Kindermann
Status:
abgeschlossen
Jahr:
2017

Beschreibung:

Es soll ein Algorithmus entwickelt werden, der zu einem gegebenen Graphen eine Zeichnung (mit gradlinigen Kanten) berechnet, wobei der kleinste Winkel zweier kreuzender Kanten möglichst groß wird. Es ist sehr schwierig, dieses Problem optimal zu lösen. Aus diesem Grunde sollen verschiedene Heuristiken erarbeitet werden, die Zeichnungen mit möglichst großen Kreuzungswinkeln erzeugen. Ein möglicher Ansatz wäre es, eine solche Lösung durch simulated annealing zu finden.

Christoph Doppelbauer | 10.05.2024