Arbeitsgruppe Theoretische Informatik

Offline Dynamic Graph Drawing: Algorithmen für komplexere Graphen

Ansprechpartner: Malte Skambath 

Aufgrund der häufigen Nutzung von Graphen zur Modellierungen oder 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 als eine Folge von Zeichnungen zu erzeugen oder zu animieren. Dabei ergeben sich zusätziche Probleme. 
Es gibt bisher wenige Offline Algorithmen, die für konkrete Graphklassen unnötige Bewegungen von Knoten verhindern [1]. In [1] wurde gezeigt, dass unter gewissen Einschränkungen solche Ansätze möglich und der rekursive Algorithmus von Reingold und Tilford [2] verallgemeinert.

In dieser Arbeit sollen neue Ansätze/Algorithmen beziehungsweise deren Machbarkeit für komplexere Graphklassen wie seriell-parallele Graphen untersucht werden.
Diese können ggf. rekursive Layoutstrategien für statische Graphen basieren und verallgmeinern.

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