Algorithmic Methods for Crossing Numbers and other Non-planarity Measures
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
(See online at https://doi.org/10.4230/LIPIcs.ESA.2016.29) - Inserting Multiple Edges into a Planar Graph. Journal of Combinatorial Optimization 33(4):1183–1225, 2017
M. Chimani, P. Hlinĕný
(See online at https://doi.org/10.1007/s10878-016-0030-z) - Crossing Numbers and Stress of Random Graphs. Proc. GD 2018, LNCS 11282, 255–268, 2018
M. Chimani, H. Döring, M. Reitzner
(See online at https://doi.org/10.1007/978-3-030-04414-5_18) - 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
(See online at https://doi.org/10.4230/LIPIcs.ESA.2018.19) - 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
(See online at https://doi.org/10.1145/3320344) - Stronger ILPs for the Graph Genus Problem. Proc. ESA 2019, LIPIcs 144, 30:1-30:15, 2019
M. Chimani, T. Wiedera
(See online at https://doi.org/10.4230/LIPIcs.ESA.2019.30) - Crossing Number for Graphs with Bounded Pathwidth. Algorithmica 82(2):355–384, 2020
T. Biedl, M. Chimani, M. Derka, P. Mutzel
(See online at https://doi.org/10.1007/s00453-019-00653-x) - Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics. Proc. GD 2021, LNCS, 2021
M. Chimani, M. Ilsen, T. Wiedera
(See online at https://doi.org/10.1007/978-3-030-92931-2_3)
