Arbeitsgruppe Theoretische Informatik

Offline Dynamic Graph Drawing: Algorithmen für komplexere Graphen

Ansprechpartner: Malte Skambath 

Aufgrund der häufigen Nutzung von Graphen zur Modellierungen, sowie für Datenstrukturen ist das automatisierte Zeichnen von Graphen [3]
in übersichtlicher und "schöner" Form wünschenswert. Neben statischen Graphen bietet es sich bei zeitlich veränderlichen Graphen an eine Folge von Zeichnungen zu erzeugen oder zu animieren. Dabei ergeben sich zusätziche Probleme. 
Es gibt bisher wenige Offline Algorithmen, welche den vollständigen Zeitverlauf eines Graphens kennen, die für spezifische Graphklassen unnötige Bewegungen von Knoten verhindern [1]. In [1] wurde gezeigt, dass unter gewissen Einschränkungen solche Ansätze möglich sind.

In dieser Arbeit sollen neue Ansätze/Algorithmen beziehungsweise deren Machbarkeit für komplexere Graphklassen wie seriell-parallele Graphen,
die optimalerweise auf rekursiven Layoutstrategien für statische Graphen basieren untersucht werden.

Quellen

  1. M. Skambath and T. Tantau, 
    Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
    In Proc. of the 24th International Symposium on Graph Drawing & Network Visualization 2016 (GD2016),
    in Lecture Notes in Computer Science Vol. 9801, p. 572-586, Springer-Verlag, 2016. 
    https://arxiv.org/abs/1608.08385
  2. E. M. Reingold, J. S Tilford,
    Tidier Drawings of Trees. 
    IEEE Transactions on Software Engineering. Vol. 7, Issue 2, 1981.
  3. Wikipedia: Graph Drawing