Neue Modelle und Methoden zum effektiven orthogonalen Layout von Graphen
Zusammenfassung der Projektergebnisse
Graph Drawing ist ein sehr aktives Gebiet, das sich mit der sinnvollen Visualisierung von Graphen in der Ebene beschäftigt. Das interdisziplinäre Gebiet vereint Zweige aus der Graphentheorie, der Kombinatorik, der Algorithmik, den Anwendungen und der Benutzerforschung. Während mehrere grundlegende Modelle und Methoden etabliert wurden, sind die praktischen Anforderungen oft nicht berücksichtigt worden. Daher müssen die Modelle verfeinert, analysiert und erforscht werden. Das bekannteste Modell ist das orthogonale Modell, bei dem die Kanten aus horizontalen oder vertikalen Liniensegmenten bestehen und höchstens ein Kantensegment auf jeder der vier möglichen Seiten eines Knotens endet. Das vorliegende Projekt befasste sich mit möglichen Erweiterungen. Wir starteten mit zwei neuen Ansätzen. Im ersten Modell, dem so genannten Smooth Drawing Model (Smog), werden anstelle von achsenparallelen Liniensegmenten Kreisbögen verwendet, die sich an einer gemeinsamen Tangente nahtlos anschließen. Das zweite Modell wird als Slanted Drawing Modell (Slog) bezeichnet. Hier werden die traditionellen 90°-Knicke durch dazwischenliegende diagonale Segmente ersetzt, so daß nur 135°-Knicke zulässig sind, und Kreuzungen werden sichtbarer gemacht, da sie nur zwischen diagonalen Segmenten zulässig sind. In beiden Modellen befinden sich die Anschlüsse für die Kanten nach wie vor an den vier möglichen Seiten der Knoten. Wir wollten vom traditionellen orthogonalen Modell so viele Ergebnisse wie möglich auf die neuen Modelle übertragen und ihre Vorteile demonstrieren und quantifizieren. In der ersten Projektphase konzentrierten wir uns auf diese beiden Modelle, insbesondere auf die Minimierung der Segmentanzahl pro Kante (Knicken), die verwendete Fläche, die Komplexität der Layout-Algorithmen und darüber hinaus auf die Untersuchung von Erweiterungsvarianten. Beide Modelle haben ihre Nachteile (z.B. großer Flächenverbrauch), aber auch schöne Eigenschaften, die übersichtlichere Layouts ermöglichen. Die von uns untersuchten Varianten weisen ebenfalls deutliche Vorteile auf, wenngleich Fragen zur Realisierbarkeit offen bleiben und die Modelle hinsichtlich ihrer Robustheit und Flexibilität für praktische Anwendungen geprüft werden müssen. In der zweiten Projektphase haben wir unsere Forschung zu Erweiterungen des ursprünglichen orthogonalen Modells ausgedehnt, die mehr praktische Aspekte berücksichtigen: Graphenlayouts mit Knoten hohen Grades erfordern viele verschiedene Steigungen auf den Kantensegmenten, wobei die Minimierung der Anzahl der Steigungen die Einheitlichkeit des Layouts unterstützt. Eine andere Richtung, die wir verfolgt haben, sind die sogenannten RAC-Zeichnungen, bei denen die Kreuzungen rechtwinklig sein müssen, die Steigungen der Kanten aber nicht eingeschränkt sind. Insbesondere haben wir Fortschritte bei der Beziehung zwischen Flächenverbrauch und Knicken sowie bei Layouts für Graphen mit begrenztem Grad gemacht. Hinsichtlich des Smog-Modells waren die Layouts, die wir ursprünglich untersucht haben, nur planar, und der Aspekt von Kantenkreuzungen war ganz offen. Dies war ein wichtiger Punkt in unserer zweiten Projektphase.
Projektbezogene Publikationen (Auswahl)
-
Slanted Orthogonal Drawings: Model, Algorithms and Evaluations. Journal of Graph Algorithms and Applications, 18(3), 459-489.
Bekos, Michael A.; Kaufmann, Michael; Krug, Robert; Ludwig, Thorsten; Näher, Stefan & Roselli, Vincenzo
-
Smooth Orthogonal Drawings of Planar Graphs. Lecture Notes in Computer Science (2014), 144-155. Springer Berlin Heidelberg.
Alam, Muhammad Jawaherul; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Kobourov, Stephen G. & Wolff, Alexander
-
The Effect of Almost-Empty Faces on Planar Kandinsky Drawings. Lecture Notes in Computer Science (2015), 352-364. Springer International Publishing.
Bekos, Michael A.; Kaufmann, Michael; Krug, Robert & Siebenhaller, Martin
-
A Universal Slope Set for 1-Bend Planar Drawings. SoCG 2017: 9:1-9:16
Angelini, Patrizio; Bekos, Michael A.; Liotta, Giuseppe & Montecchiani, Fabrizio
-
On the Total Number of Bends for Planar Octilinear Drawings. Journal of Graph Algorithms and Applications, 21(4), 709-730.
Bekos, Michael; Kaufmann, Michael & Krug, Robert
-
On RAC Drawings of Graphs with One Bend per Edge. Lecture Notes in Computer Science (2018), 123-136. Springer International Publishing.
Angelini, Patrizio; Bekos, Michael A.; Förster, Henry & Kaufmann, Michael
-
On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings. Algorithmica, 81(5), 2046-2071.
Bekos, Michael A.; Förster, Henry & Kaufmann, Michael
-
Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity. Lecture Notes in Computer Science (2018), 509-523. Springer International Publishing.
Argyriou, Evmorfia; Cornelsen, Sabine; Förster, Henry; Kaufmann, Michael; Nöllenburg, Martin; Okamoto, Yoshio; Raftopoulou, Chrysanthi & Wolff, Alexander
-
Universal Slope Sets for Upward Planar Drawings. Lecture Notes in Computer Science (2018), 77-91. Springer International Publishing.
Bekos, Michael A.; Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe & Montecchiani, Fabrizio
-
A Heuristic Approach Towards Drawings of Graphs With High Crossing Resolution. The Computer Journal, 64(1), 7-26.
Bekos, Michael A; Förster, Henry; Geckeler, Christian; Holländer, Lukas; Kaufmann, Michael; Spallek, Amadäus M & Splett, Jan
-
Greedy rectilinear drawings. Theoretical Computer Science, 795(2019, 11), 375-397.
Angelini, Patrizio; Bekos, Michael A.; Didimo, Walter; Grilli, Luca; Kindermann, Philipp; Mchedlidze, Tamara; Prutkin, Roman; Symvonis, Antonios & Tappini, Alessandra
-
On Arrangements of Orthogonal Circles. Lecture Notes in Computer Science (2019), 216-229. Springer International Publishing.
Chaplick, Steven; Förster, Henry; Kryven, Myroslav & Wolff, Alexander
-
Drawing
Graphs with Circular Arcs and Right-Angle Crossings. SWAT 2020: 21:1-21:14,
Chaplick, Steven; Förster, Henry; Kryven, Myroslav & Wolff, Alexander
-
Monotone Arc Diagrams with few Biarcs. CoRR abs/2003.05332 (2020)
Chaplick, Steven; Förster, Henry; Hoffmann, Michael & Kaufmann, Michael
-
On Compact RAC Drawings. ESA 2020: 53:1- 53:21
Förster, Henry & Kaufmann, Michael
-
On Strict (Outer-)Confluent Graphs. Journal of Graph Algorithms and Applications, 25(1), 481-512.
Förster, Henry; Ganian, Robert; Klute, Fabian & Nöllenburg, Martin
-
Using the Metro-Map Metaphor for Drawing Hypergraphs. Lecture Notes in Computer Science (2021), 361-372. Springer International Publishing.
Frank, Fabian; Kaufmann, Michael; Kobourov, Stephen; Mchedlidze, Tamara; Pupyrev, Sergey; Ueckerdt, Torsten & Wolff, Alexander
-
RAC Drawings of Graphs with Low Degree. MFCS 2022: 11:1-11:15
Angelini, Patrizio; Bekos, Michael A.; Katheder, Julia; Kaufmann, Michael & Pfister, Maximilian
