Graph Drawing and Evolutionary Computation - A Theoretical Approach

• Applicants: Professor Dr. Ignaz Rutter; Professor Dr. Dirk Sudholt
• Subject Area: Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 577782724

Graphs are a fundamental tool in the digital era for modelling relationships in domains such as social networks, software systems, and biological data. Effective graph visualisation helps users interpret complex structures, and Graph Drawing is the field that develops algorithms for computing such layouts. Key aesthetic criteria include minimising edge crossings and bends, optimising angles, and ensuring compactness. These goals often conflict, making layout generation a multi-objective optimisation problem that is typically NP-hard. Evolutionary algorithms (EAs) are powerful, population-based metaheuristics inspired by the principles of natural evolution. They are versatile, adaptive, and their population-based nature makes them particularly well-suited to multi-objective optimisation, as populations can naturally store trade-offs between conflicting objectives. EAs are also ideal for problems where the structure is complex, unknown, or hard to model. Despite promising empirical results in graph drawing, it often remains unclear when and why EAs perform well. This lack of a theoretical foundation constitutes a major obstacle to their broader adoption. This project, a close collaboration between experts on graph drawing and theory of evolutionary computation, aims to remove this obstacle and to bridge the gap between these two research fields. We apply rigorous runtime analysis, originating in theoretical computer science and probability theory, to derive proven guarantees on the time needed for EAs to evolve high-quality graph layouts. This enables general, mathematically sound performance statements and supports the principled design of effective algorithms. We will focus on drawing styles with structured yet complex solution spaces, such as layered drawings, where graphs are drawn on horizontal layers, with upward-pointing edges. From the graph drawing perspective, we aim to understand how EA design choices—such as the choice of operators (e.g. mutation and crossover) and parameters (e.g. population size)—affect layout quality, and to develop a well-founded design framework. This understanding will inform the development of EAs that combine conceptual simplicity with provable performance guarantees. These algorithms will be tailored to graph drawing tasks and capable of producing diverse, high-quality layouts, offering both robustness and creative flexibility. From the perspective of EA theory, graph drawing presents novel challenges that will spur the development of more powerful analytical tools and operator designs. The feasibility and significance of this research are underscored by the proposers’ joint preparatory work, which received a Best Paper Award at ACM’s flagship conference on evolutionary computation.

• DFG Programme: Research Grants
• International Connection: USA
• Cooperation Partner: Professor Dr. Andrew M. Sutton