Project Details
Projekt Print View

Computing Beyond Planarity

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
 
 

Additional Information

Textvergrößerung und Kontrastanpassung