Funded by the Deutsche Forschungsgemeinschaft (DFG), project no. 577782724 from June 2026
This project builds a rigorous theoretical foundation at the intersection of Graph Drawing and Evolutionary Algorithms (EAs). EAs are a powerful and versatile family of optimisation methods inspired by biological evolution, which have been successfully applied to a wide range of graph drawing problems for over 35 years. By combining this practical success with the analytical methods of runtime analysis, we derive provable performance guarantees for EA-based graph drawing algorithms, uniting conceptual simplicity with mathematical precision and predictive power.
The project focuses on layered graph drawings and the widely used Sugiyama Framework, addressing core problems such as crossing minimisation, cycle removal, and layer assignment. Beyond layered drawings, we also investigate other drawing styles such as circular drawings and book embeddings. From the perspective of EA theory, graph drawing introduces a rich class of optimisation problems that go beyond standard representations, offering new challenges and opportunities for advancing the field.
The project is a close collaboration between the Chair of Theoretical Computer Science (PI: Ignaz Rutter) and the Chair of Algorithms for Intelligent Systems (PI: Dirk Sudholt [URL]), both at the University of Passau.
Funded by the Deutsche Forschungsgemeinschaft (DFG), from October 2024
Graph drawing is concerned with computing geometric representations of graphs that support human understanding. A central concept is planarity: a graph is planar if it can be drawn without edge crossings. Planarity is well-understood and underlies many efficient algorithms in network visualization.
In practice, however, most real-world networks are non-planar. Beyond-planar graph classes — such as 1-planar, k-planar, fan-planar, RAC, and quasi-planar graphs — generalize planarity by allowing crossings, but restricting how they may occur (e.g., each edge may be crossed at most once, or all crossings must be at right angles). While the combinatorial properties of these classes are increasingly well understood, their algorithmic foundations remain largely underdeveloped: for almost all relevant beyond-planar graph classes, even deciding whether a given graph belongs to the class is NP-hard, and practical algorithms are largely missing.
The goal of this project is to develop an algorithmic toolbox for recognizing, embedding, and drawing beyond-planar graphs. We pursue this along four lines of research: parameterized and approximation algorithms for recognition, exact and heuristic algorithms for practical deployment, geometric and topological realizability of crossing structures, and beyond-planarity concepts for directed graphs. The project is carried out in collaboration with partners at the Universities of Tübingen, Trier, Roma Tre, TU Wien, Perugia, and Utrecht.
(DFG/GAČR, October 2019 – November 2023, with Alexander Wolff, Univ. Würzburg, and Jiří Fiala, Charles Univ. Prague)
Graphs and networks can be represented geometrically by assigning geometric objects — such as intervals, circles, or more complex shapes — to vertices, and encoding adjacency through intersections or mutual visibility between these objects. Such representations arise naturally in many application domains and are a central topic in discrete mathematics and theoretical computer science.
This project studies the algorithmic and combinatorial properties of several families of geometric representations. The research directions include: extending a given partial representation to a full one; finding simultaneous compatible representations for multiple related graphs; minimising the number of obstacles needed in visibility representations; analysing H-topological intersection graphs as a parametric generalisation of interval graphs; computing or approximating the maximum number of edge crossings in a straight-line drawing; and characterising graphs that admit low-ply drawings, in which no point of the plane is covered by too many vertex disks.
