Algorithms for Interaction in Graph Drawing
Final Report Abstract
Ziel des Projektes war es die Lücke zwischen vollautomatischen Verfahren zum Zeichnen von Graphen und aufwendigen manuellen Manipulationen von Graphzeichnungen zu verringern. Wir haben im Rahmen dieses Projektes verschiedene Modelle zur Interaktion mit Zeichnungen entworfen und untersucht. Unsere theoretischen Beiträge zeigen die Grenzen der Modelle und für eine breite Klasse von Instanzen, ob sich bestimmte Zeichnungen realisieren lassen. Parallel zu der theoretischen Betrachtung haben wir uns mit der effizienten Implementierung von Methoden zur Manipulation von Zeichnungen beschäftigt. Die entwickelten Methoden können entweder in interaktiven Szenarien angewendet werden oder als vollautomatisches Werkzeug dienen. Da unsere Algorithmen auf geometrischen Konstruktionen basieren, können diese leicht so angepasst werden, dass weitere Benutzeranforderungen berücksichtigt werden. Wir haben die Grundsteine für einen interaktiven Editor gesetzt, allerdings andere Themen im Laufe des Projektes priorisiert, so dass wir die Entwicklung des Editors nicht erfolgreich abschließen konnten. Mit unseren Resultaten haben wir entschieden dazu beigetragen, interaktive Methoden zum Graphzeichnen zu entwickeln. Insbesondere aus angewandter Perspektive bietet der Bereich noch vielversprechende Aufgabenstellungen.
Publications
- Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model. In: Proceedings of the 22nd Annual European Symposium on Algorithms (ESA’14). Hrsg. von Andreas S. Schulz und Dorothea Wagner. Bd. 8737. Lecture Notes in Computer Science. 2014, S. 161– 172
Thomas Bläsius, Guido Brückner und Ignaz Rutter
(See online at https://doi.org/10.1007/978-3-662-44777-2_14) - Optimal Orthogonal Graph Drawing with Convex Bend Costs. In: ACM Transactions on Algorithms 12.3 (2016), 33:1–33:32
Thomas Bläsius, Ignaz Rutter und Dorothea Wagner
(See online at https://doi.org/10.1145/2838736) - Orthogonal Graph Drawing with Inflexible Edges. In: Computational Geometry 55 (2016), S. 26–40
Thomas Bläsius, Sebastian Lehmann und Ignaz Rutter
(See online at https://doi.org/10.1016/j.comgeo.2016.03.001) - Aligned Drawings of Planar Graphs. In: Journal of Graph Algorithms and Applications 22.3 (Special Issue) (2018), S. 401–429
Tamara Mchedlidze, Marcel Radermacher und Ignaz Rutter
(See online at https://doi.org/10.7155/jgaa.00475) - Inserting an Edge into a Geometric Embedding. In: Proceedings of the 26th International Symposium on Graph Drawing (GD’18). Hrsg. von Therese C. Biedl und Andreas Kerren. Bd. 11282. Lecture Notes in Computer Science. Springer International Publishing, 2018, S. 402–415
Marcel Radermacher und Ignaz Rutter
(See online at https://doi.org/10.1007/978-3-030-04414-5_29) - Geometric Heuristics for Rectilinear Crossing Minimization. In: Journal of Experimental Algorithmics 24.1 (2019), 1.12:1–1.12:21
Klara Reichard, Marcel Radermacher, Ignaz Rutter und Dorothea Wagner
(See online at https://doi.org/10.1145/3325861)
