Kreisbogen-Visualisierung von Bäumen
Studien- oder Diplomarbeit
Bei der Visualisierung von Graphen, insbesondere von Bäumen, werden meist die folgenden Gütekriterien gefordert:
- Planarität
- geradlinige Kanten
- optimale Winkelauflösung
- niedriger (polynomieller) Flächenbedarf
Betrachtet man geordnete Bäume, bei denen die Reihenfolge der Nachbarknoten vorgegeben ist, gibt es jedoch eine einfache Familie von Bäumen, die nicht alle Kriterien gleichzeitig erfüllen können.
Ein Ausweg ist, Kanten als Kreisbögen zu zeichnen. Solche Zeichnungen sind inspiriert durch die Netzzeichnungen des Künstlers Mark Lombardi. Der exisitierende Zeichenalgorithmus lässt aber vor allem in der Praxis noch viel Raum für Verbesserungen.
Art
Studien- oder Diplomarbeit
Ziele
Ziel der Arbeit ist zunächst die Implementierung des existierenden Zeichenalgorithmus und die Entwicklung neuer Techniken zur Reduzierung des Flächenbedarfs. Die Verbesserung der theoretischen Schranken für die Fläche sowie experimentelle Untersuchungen zur Qualität der Zeichnungen sind weitere mögliche Fragestellungen.
Voraussetzung
fundierte algorithmische Kenntnisse und Interesse für geometrische Fragestellungen