Algorithms for Interaction in Graph Drawing

• Applicant: Professorin Dr. Dorothea Wagner
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 244429338

• Final Report Year: 2020

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
  Bläsius, Thomas; Brückner, Guido & Rutter, Ignaz
  
• Optimal Orthogonal Graph Drawing with Convex Bend Costs. In: ACM Transactions on Algorithms 12.3 (2016), 33:1–33:32
  Bläsius, Thomas; Rutter, Ignaz & Wagner, Dorothea
  
• Orthogonal Graph Drawing with Inflexible Edges. In: Computational Geometry 55 (2016), S. 26–40
  Bläsius, Thomas; Lehmann, Sebastian & Rutter, Ignaz
  
• Aligned Drawings of Planar Graphs. In: Journal of Graph Algorithms and Applications 22.3 (Special Issue) (2018), S. 401–429
  Mchedlidze, Tamara; Radermacher, Marcel & Rutter, Ignaz
  
• 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
  Radermacher, Marcel & Rutter, Ignaz
  
• 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