Algorithmen für die Interaktion im Graphenzeichnen

• Antragstellerin: Professorin Dr. Dorothea Wagner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 244429338

• Erstellungsjahr: 2020

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1145/​3325861)