Effizientes Zeichnen orthogonaler Netzwerke für Datenflussdiagramme

Betreuer/in:            Matthias Mnich           
Dekanat/Institut:   Elektrotechnik, Informatik, Mathematik / Institut für Algorithmen und Komplexität (E-11)           

E-Mail:   mmnich@tuhh.de

Motivation: Das Zeichnen von Netzwerken befasst sich mit der Entwicklung von Methoden zum automatischen Zeichnen von Graphen, um wichtige Merkmale solcher Netzwerke hervorzuheben und ästhetisch ansprechende Visualisierungen zu erzeugen. Zum Beispiel, wenn das Netzwerk kreuzungsfrei gezeichnet werden kann, dann ist es wünschenswert, eine solche Zeichnung zu generieren in der sich keine zwei Kanten kreuzen, und wenn sich die Kanten in der Zeichnung stark biegen, ist das Optimierungsziel die Biegeminimierung.

In dieser Bachlor- oder Master-Arbeit geht es um orthogonale Zeichnungen, in denen Kanten durch horizontale und vertikale Segmente dargestellt werden. Solche Zeichnungen werden häufig in Anwendungen wie Datenbanksystemen (E-R-Diagrammen) und Software-Engineering (Datenflussdiagramme) verwendet, sowie Schaltungsdesign (Schaltpläne). In solchen Anwendungen versucht man die Anzahl der Biegungen in den Zeichnungen zu minimieren, um die Komplexität für den Betrachter gering zu halten.

Methoden: In der Arbeit „Computing Orthogonal Drawings in a Variable Embedding Setting” (https://link.springer.com/chapter/10.1007%2F3-540-49381-6_10) wird ein Verfahren vorgestellt, um orthogonale Zeichnungen mit der kleinsten Anzahl an Biegungen zu finden. Die Laufzeit des Verfahrens ist dabei effizient in der Größe des Netzwerks und hängt exponentiell nur von der Anzahl der Knoten mit Grad mindestens 4 ab.

Projektziele und Arbeitspakete:

  • Durcharbeiten der Arbeit „Computing Orthogonal Drawings in a Variable Embedding Setting” (10 Seiten) und Ausarbeiten der fehlenden Zwischenschritte
  • Korrektheits- und Laufzeitanalyse des Verfahrens
  • Untersuchung des Verfahrens auf mögliche Verbesserungen der Laufzeit mittels moderner Verfahren wie effizienten Datenreduktionsregeln und balancierten planarer Separatoren
  • Umfangreiche Tests und Dokumentation experimenteller Ergebnisse der gefundenen Datenreduktionen im Hinblick auf den Rechen- und Speicheraufwand im Vergleich zu Experimenten im Artikel.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.