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

• Final Report Year: 2022

Final Report Abstract

In dem Projekt betrachteten wir vor allem algorithmische Methoden um Nichtplanaritätsmaße von Graphen effizient(er) zu berechnen. Wir spannten ein Gamut zwischen heuristischen, approximativen und exakten Verfahren auf und betrachteten nicht nur das bekannte Kreuzungszahlproblem, sondern auch die Frage nach maximalen planaren Teilgraphen, dem Graphgenus, sowie diverser weiterer Maße. Die Highlights waren dabei sicherlich • ein ILP-basiertes System zum automatischen Erzeugen einfach validierbarer Kreuzungszahlbeweise; • der FPT Algorithmus zum kreuzungsminimalen Einfügen einer konstanten Anzahl von Kanten in einen planaren Graphen; • die ersten Kreuzungszahl-Approximationen auf Basis einer Graphdekomposition, nämlich der Pfadzerlegung; • die derzeit in der Praxis stärksten Heuristiken für das Kreuzungszahlproblem, basierend auf dem Einfügen von Sternen in festen Einbettungen, und der damit einhergehenden Beschleunigung durch den möglichen Verzicht auf die komplexe SPQR-Baum Datenstrukturen; • die erste mathematische Verknüpfung von zufälligen geometrischen Graphen, ihrer Kreuzungszahl, einfacher Approximierbarkeit, und stressminimalen Zeichnungen; • die sowohl in Theorie als auch Praxis deutliche Verstärkung des ILPs zur Berechnung maximaler planarer Teilgraphen mittels Kreisliftings und -ungleichungen; und • die ersten praxistauglichen Verfahren zum exakten Berechnen des Graphgenus, obgleich für das Problem noch nicht einmal taugliche Heuristiken bekannt sind. Diese Ergebnisse wurden abgerundet durch diverse flankierende Resultate, sodass 24 einschlägige international publizierte Publikationen, zzgl. 2 Dissertationen, entstanden.

Publications

• An ILP-based Proof System for the Crossing Number Problem. Proc. ESA 2016, LIPIcs 57, 29:1–29:13, 2016
  M. Chimani, T. Wiedera
  
• Inserting Multiple Edges into a Planar Graph. Journal of Combinatorial Optimization 33(4):1183–1225, 2017
  M. Chimani, P. Hlinĕný
  
• Crossing Numbers and Stress of Random Graphs. Proc. GD 2018, LNCS 11282, 255–268, 2018
  M. Chimani, H. Döring, M. Reitzner
  
• Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast. Proc. ESA 2018, LIPIcs 112, 19:1-19:14, 2018
  M. Chimani, T. Wiedera
  
• Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments. ACM J. Exp. Algorithmics 24(1):2.1:1–2.1:21, 2019
  M. Chimani, I. Hedtke, T. Wiedera
  
• Stronger ILPs for the Graph Genus Problem. Proc. ESA 2019, LIPIcs 144, 30:1-30:15, 2019
  M. Chimani, T. Wiedera
  
• Crossing Number for Graphs with Bounded Pathwidth. Algorithmica 82(2):355–384, 2020
  T. Biedl, M. Chimani, M. Derka, P. Mutzel
  
• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics. Proc. GD 2021, LNCS, 2021
  M. Chimani, M. Ilsen, T. Wiedera