New Models and Methods for the Effective Orthogonal Layout of Graphs
Final Report Abstract
Graph drawing is a very active field which concerns about the meaningful visualization of graph in the plane. The interdisciplinary field combines branches from graph theory, combinatorics, algorithms, applications, and user studies. While several fundamental models and methods have been established, very often practical needs have not been taken into account. Hence the models have to be refined, analyzed and explored. The most prominent model is the orthogonal one, where edges consist of horizontal or vertical line segments, and at most one edge segment is incident to each of the four possible sides of its end vertex. The project was concerned about possible extensions. We started with two models. In the first one, called smooth drawing model (Smog), instead of axis-parallel line segments, we use circular arcs that smoothly connect at a common tangent. The second model is called slanted drawing model (Slog). Here the traditional 90°-bends are replaced by intermediate diagonal segments such that only 135° bends are allowed, and crossings are made more visible as we allow them only between diagonal segments. In both models, the ports for the edges are still at the top, bottom, left and right side of each vertex. We planned to transfer as many results as possible from the traditional orthogonal model to the new models, and to demonstrate and quantify their advantages. In the first project period, we focused on the understanding of the two models, in particular, the minimization of the number of segments per edge (bends), the used area, the complexity of layout algorithms and furthermore the study of extensions. Both models had their drawbacks (e.g., extensive area consumption), but also nice features that allow clearer layouts. The variants that we considered also clearly show several advantages, although questions about the realizability remain open and the models have to be approved concerning their robustness and flexibility to the needs of practical applications. For the second project period, we extended our research on the extensions of the original orthogonal model towards criteria that take more practical aspects into account: Graph layout with vertices of high degree require many different slopes on the edge segments, nevertheless minimizing the number of slopes supports the uniformity of the layout. Another direction that we followed are the so-called RAC drawings, where the crossings are required to be at right angles, but the slopes of the edges are not restricted. In particular, we made progress on the relation between area consumption and bends, and on realizability problems for bounded degree graphs. On the other hand, the Smog layouts that we originally studied were just planar, and it has been open how to realize edge crossings. That has been a major point in our second project period.
Publications
-
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
