Algorithmische Methoden für Kreuzungszahlen und andere Nichtplanaritätsmaße
Zusammenfassung der Projektergebnisse
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.
Projektbezogene Publikationen (Auswahl)
- An ILP-based Proof System for the Crossing Number Problem. Proc. ESA 2016, LIPIcs 57, 29:1–29:13, 2016
M. Chimani, T. Wiedera
(Siehe online unter 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ý
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter https://doi.org/10.1007/978-3-030-92931-2_3)
