Drawing Graphs with Low Visual Complexity
Final Report Abstract
Das Zeichnen von Graphen bzw. Netzwerken ist ein vielschichtiges algorithmisches Problem. Für die Erstellung von Zeichnungen gibt es eine Vielzahl von Entwurfskriterien, die teilweise in Konkurrenz zueinander stehen. Ein relativ neuer Ansatz ist es, die Anzahl der geometrischen Objekte, aus der eine Zeichnung zusammengesetzt ist, zu minimieren. In diesem Zusammenhang spricht man auch von Zeichnungen mit niedriger visueller Komplexität. Im Projekt wurden vordergründig zwei Fragen untersucht. Zum einen sollte geprüft werden, ob dieses Optimierungsziel wirklich gut lesbare und ästhetisch ansprechende Zeichnungen fordert, zum anderen sollten neue Algorithmen entwickelt werden, die Zeichnungen mit niedriger visueller Komplexität erzeugen. Für die Bewertung der Algorithmen war es zudem notwendig, Schranken für die visuelle Komplexität zu bestimmen. Das Hauptresultat des Projektes ist eine umfangreiche Online-Benutzerstudie. Es konnte nachgewiesen werden, dass Zeichnungen mit niedriger visueller Komplexität ihre Berechtigung haben. Der implizierte (schematische) Zeichenstil stellt eine Alternative zu anderen Stilen dar. Zeichnungen in diesem Stil haben in etwa die gleiche ästhetische Qualität wie Zeichnungen, die von gängigen anderen Algorithmen erzeugt werden. Es wurde zudem erkannt, dass die persönlichen Präferenzen sich stark unterscheiden können und von den „Seh-Gewohnheiten“ der Betrachter abhängen. Des Weiteren wurde festgestellt, dass sich Zeichnungen mit niedriger visueller Komplexität (zumindest bei gradlinigen Zeichnungen) weniger gut für einfache Aufgaben, wie das Finden von kürzesten Wegen, eignen. Fur die Durchführung der Benutzerstudie war es notwendig, neue Algorithmen zum Zeichnen von Graphen mit niedriger visueller Komplexität zu entwicklen. In diesem Zusammenhang konnten einige theoretische Ergebnisse verbessert werden; unter anderem für gradlinige Gitterzeichnungen mit niedriger visueller Komplexität (Bäume, planare 3-Bäume, planare 3-zusammenhängende Graphen) und für Zeichnungen mit Kreisbögen (Triangulierungen und planare 3-zusammenhängende Graphen). Neben den eher theoretisch motivierten Ergebnissen wurden auch eine Reihe von Heuristiken entwickelt. Hier konzentrierten sich die Untersuchungen hauptsächlich auf Bäme. Für kubische planare Graphen wurden zudem drei konzeptionell verschiedene optimale Algorithmen (bzgl. der visuellen Komplexität) (weiter-)entwickelt und deren Ergebnisse empirisch ausgewertet.
Publications
- A Tale of Two Communities: Assessing Homophily in Node-Link Diagrams, Graph Drawing and Network Visualization – 23rd International Symposium (GD), LNCS 9411, Seiten 489–501, Los Angeles, 2015
W. Meulemans und A. Schulz
(See online at https://doi.org/10.1007/978-3-319-27261-0_40) - Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms and Experiments, Journal of Graph Algorithms and Applications, Vol. 21, Num. 4, Seiten 561–588, 2017
A. Igamberdiev, W. Meulemans und A. Schulz
(See online at https://dx.doi.org/10.7155/jgaa.00430) - Drawing Planar Graphs with Few Geometric Primitives, Graph-Theoretic Concepts in Computer Science – 43rd International Workshop (WG), LNCS 10520, Seiten 316–329, Heeze, 2017
G. Hültenschmidt, P. Kindermann, W. Meulemans und A. Schulz
(See online at https://doi.org/10.1007/978-3-319-68705-6_24) - Experimental Analysis of the Accessibility of Drawings with Few Segments, Graph Drawing and Network Visualization – 24th International Symposium (GD), LNCS 10692, Seiten 52–64, Boston, 2017
P. Kindermann, W. Meulemans und A. Schulz
(See online at https://doi.org/10.1007/978-3-319-73915-1_5) - On Gallai’s Conjecture for Series-parallel Graphs and Planar 3-trees
P. Kindermann, L. Schlipf und A. Schulz
- (2019) Drawing Planar Graphs with Few Segments on a Polynomial Grid. In: Archambault D., Tóth C. (eds) Graph Drawing and Network Visualization. GD 2019. Lecture Notes in Computer Science, vol 11904. Springer, Cham. S. 416-429
P. Kindermann, T. Mchedlidze, R. Prutkin, T. Schneck und A. Symvonis
(See online at https://doi.org/10.1007/978-3-030-35802-0_32)
