Computing Beyond Planarity

• Applicant: Professor Dr. Markus Chimani
• Subject Area: Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 574443057

The crossing number is the smallest possible number of pairwise edge crossings when drawing a given graph into the plane. Planar graphs are those with crossing number 0. Beyond-planar concepts restrict the drawings w.r.t. allowed crossing patterns -- e.g., edges may only be crossed a bounded number of times, or individual edges may not be crossed by two non-adjacent edges, etc. A beyond-planar crossing number (for a given beyond-planarity concept) is the smallest number of crossings under the considered drawing restriction. This measure is both of theoretical (topological graph-theory) and practical (graph drawing) interest. In this project, we consider theoretical and practical algorithmic methods to compute beyond-planar crossing numbers: both exactly (via integer linear programs) as well as heuristically and approximatively (based on insertion- and planarization-methods).

• DFG Programme: Research Grants