Algorithmic Methods for Crossing Numbers and other Non-planarity Measures

• Applicant: Professor Dr. Markus Chimani
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 285614448

The crossing number of a graph is the smallest number of pairwise edge crossings that are necessary when drawing the graph in the plane. The problem to determine the crossing number of a graph is a classical problem in topological graph theory; it constitutes the probably best-known concept among a set of several different non-planarity measures. The study of crossing numbers is roughly 70 years old, and started out mostly in the realm of graph theory. Algorithmically, there was only slow progress in the early years. However, especially the last 10-20 years brought us several algorithmic advancements, to better understand the NP-complete crossing number problem. Nonetheless, several fundamental questions, for instance the problem's approximability, are still open. On the one hand, the aim of this project is to develop new algorithmic methods to solve the crossing number approximatively or exactly. We thereby combine theoretical research with the concepts of Algorithm Engineering, to devise schemes that are also applicable for real-world applications. On the other hand, we also consider other non-planarity measures. We want to use our crossing number experience to develop new algorithmic approaches for those. We may explicitly mention the (also NP-hard) maximum planar subgraph problem, as well as its relatives maximum induced planar subgraph/vertex deletion number and vertex splitting number. Those problems arise frequently in practice, but constitute demanding challenges for exact and approximative solution strategies.

• DFG Programme: Research Grants