Algorithmische Methoden für Kreuzungszahlen und andere Nichtplanaritätsmaße

• Antragsteller: Professor Dr. Markus Chimani
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 285614448

Die Kreuzungszahl eines Graphen ist die kleinste Anzahl an paarweisen Kantenkreuzungen die notwendig ist, um den Graphen in der Ebene zu zeichnen. Das Problem, die Kreuzungszahl zu bestimmen, ist ein klassisches Problem der topologischen Graphentheorie und der wohl bekannteste Stellvertreter einer ganzen Reihe von Maßen der Nichtplanarität. Insbesondere zu Beginn seiner 70-jährigen Geschichte wurde das Kreuzungszahlproblem vor allem aus graphentheoretischer Sicht betrachtet. Nach anfänglich eher langsamen Fortschritten von Seiten der Algorithmik, brachten insbesondere die letzten 10-20 Jahre zahlreiche algorithmische Entwicklungen, um das NP-vollständige Kreuzungszahlproblem besser zu verstehen. Dennoch sind noch immer diverse grundlegende Fragen, z.B. nach der Approximierbarkeit des Problems, unbeantwortet. Ziel dieses Projekts ist es einerseits, neue algorithmische Methoden zur approximativen und exakten Lösung des Kreuzungszahlproblems zu entwickeln. Dabei kombinieren wir theoretische Forschung mit dem Konzept des Algorithm Engineering, um Verfahren zu erhalten die in der Praxis angewandt werden können. Andererseits betrachten wir auch andere Nichtplanaritätsmaße und möchten unsere Kreuzungszahlerfahrungen in neue algorithmische Verfahren für diese einfließen lassen. Dabei sei zum Beispiel das (ebenfalls NP-schwere) Problem des Maximum Planar Subgraph, sowie diverse Varianten wie Maximum Induced Planar Subgraph/Vertex Deletion Number oder Vertex Splitting Number explizit erwähnt. Diese Probleme treten in der Praxis häufig auf, stellen insbesondere bzgl. exakten und approximativen Verfahren jedoch gewichtige Herausforderungen da.

• DFG-Verfahren: Sachbeihilfen