Servicenavigation

Project Details

Back

Projekt Print View

New Models and Methods for the Effective Orthogonal Layout of Graphs

Subject Area Theoretical Computer Science
Term from 2014 to 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 249458560
 
Final Report Year 2023

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

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung