New Models and Methods for the Effective Orthogonal Layout of Graphs

• Applicant: Professor Michael Kaufmann, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 249458560

Orthogonal graph drawing is an intensively studied and well-established model for drawing graphs, which traces back to VLSI layouts and floor-planning applications. Due to its high importance in practical applications, several efficient algorithms providing good aesthetics and good readability have been proposed over the years. However, due to the inherent limitations but also because of the simplicity of the model, there exist also some drawbacks that seem to be unavoidable. In the first phase of this project, we identified these drawbacks and suggested two main alternative models. The first model is the smooth orthogonal graph drawing model (Smog, for short), which combines the rigidity and clarity of orthogonal layouts with the artistic style and aesthetic appeal of the so-called Lombardi drawings.The second model is the slanted orthogonal drawing model (Slog, for short), which allows diagonal segments, while keeping the original orthogonal ports, in particular to simplify the recognizability of the crossings. In the first phase of the project, the research mainly focused on introducing methodological foundations. In the second phase, we plan to further continue our theoretical study and also to apply the knowledge we gained in the first phase of the project to diverse application areas aiming in integrating domain-specific requirements in our models.

• DFG Programme: Research Grants
• Co-Investigator: Professor Dr. Michael Bekos