Algorithms for Beyond-Planar Graph Drawing

• Applicant: Professor Dr. Ignaz Rutter
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 541433306

Planar graphs, i.e., graphs that can be drawn without crossings in the plane, form the backbone of many techniques in graph visualization. However, many graphs that arise in practical applications are non-planar. They are, however, usually sparse and close to planarity in the sense that they have drawings where the crossings are well distributed. To increase direct applicability to real-world instances and to overcome the limitations imposed by the concept of planarity, the field of Graph Drawing has started to investigate so-called beyond-planar graphs, which are graph classes that are non-planar but in some sense close to planar. An example are 1-planar graphs, which have a drawing where each edge has at most one crossing. Today, several classes of beyond-planar graphs are known, and they have been the subject of intense research. There is a vast amount of literature that answers many key questions, such as determining the maximum edge density and the comparison of different classes of beyond-planar graphs. A major current roadblock to transferring these results into applications is the fact that for all relevant beyond-planar graph classes, the complexity of the corresponding recognition problem is either unknown or has turned out to be NP-complete, and so far progress has only been made in the form of polynomial-time algorithms that are restricted to very special cases. The goal of this project is to develop an algorithmic toolbox for working with beyond-planar graphs. To this end, we will study beyond-planar graphs with a strong focus on algorithmic questions concerning recognition and drawing problems. Our goal is to develop algorithms that apply to a wide range of instances. To overcome the known hardness results for the recognition problems, we will employ algorithmic techniques such as approximation algorithms, parameterized algorithms as well as exact and heuristic approaches.

• DFG Programme: Research Grants