Institut für Theoretische Informatik, Algorithmik

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

Kontakt