Arrangements und Graphenzeichen

Arrangements von geometrischen Objekten und Zeichnungen von Graphen bilden einen Kernbestandteil der modernen diskreten und algorithmischen Geometrie. Sie stellen flexible Werkzeuge für zahlreiche Anwendungen in Mathematik und Informatik bereit, da sich viele wichtige Fragestellungen auf geometrischen Objekten als Arrangements und/oder Graphen modellieren lassen. Eine detaillierte Untersuchung dieser Objekte und ihrer Eigenschaften verspricht daher, Auswirkungen in einem weiten Bereich von Anwendungsgebieten zu haben. Das vorliegende DACH-Projekt Arrangements und Graphenzeichnen vernetzt Arbeitsgruppen, die bereits im European collaborative research programme EuroGIGA erfolgreich zusammengearbeitet haben. Im aktuellen Projekt möchten wir die Beziehungen zwischen verschiedenen Arten von Arrangements und Zeichnungen untersuchen, zusammen mit ihren abstrakten Darstellungen und ihren algorithmischen Eigenschaften. Dazu haben wir eine Reihe von anspruchsvollen Forschungsfragen aus den folgenden vier Schwerpunkten zusammengestellt: (A) Arrangements von Geraden und Pseudogeraden, (B) Zeichnungen von Graphen, (C) Struktur von Schnitten und (D) Planare und fast-planare Strukturen. Die Zielsetzung dieses Projekts ist es, neue Erkenntnisse und ein tieferes Verständnis in diesen Bereichen zu gewinnen, um gemeinsam einige ihrer seit langem offenen Fragen in Angriff zu nehmen. Diese Fragen sind äußerst anspruchsvoll aber von zentraler Bedeutung, sodass sogar Teillösungen nachhaltige Auswirkungen haben werden. Jeder der vier Standorte des vorgeschlagenen DACH-Projekts (TU Berlin, FU Berlin, ETH Zürich und TU Graz) wird sich auf eine Teilmenge dieser Schwerpunkte konzentrieren, so dass jeder Schwerpunkt durch mindestens zwei Standorte abgedeckt ist.

Zentrales Thema des trilateralen D-A-CH Projekts "Arrangements und Graphenzeichnen" sind Arrangements von geometrischen Objekten sowie Zeichnungen von Graphen, zwei fundamentalen Konzepten im Kernbereich der diskreten und algorithmischen Geometrie. Das Projekt bestand aus vier Teilprojekten, geleitet von Stefan Felsner (TU Berlin), Wolfgang Mulzer (FU Berlin), Michael Hoffmann (ETH Zürich) und Birgit Vogtenhuber (TU Graz). Der Fokus des Projekts lag auf kombinatorischen, existenziellen und komplexitätstheoretischen Fragestellungen und hatte das ambitionierte Ziel, das Wissen über die betrachteten Strukturen relevant zu erweitern und im Speziellen auch seit langem offene Fragen in Angriff zu nehmen. Dazu haben wir anspruchsvolle Forschungsfragen aus vier Schwerpunkten zusammengestellt, nämlich (A) Arrangements, (B) Zeichnungen von Graphen, (C) Struktur von Schnitten und (D) planare und fast-planare Strukturen. Statt jedem Teilprojekt einen dieser Schwerpunkte zuzuordnen, war geplant, die Forschung an allen vier Schwerpunkten in intensiver gruppenübergreifender Form sowie unter Einbindung externer Kooperationspartner durchzuführen. Mit Freude und Stolz dürfen wir berichten dass dieser Plan sehr erfolgreich umgesetzt wurde. Zu vielen Problemstellungen konnten neue Erkenntnisse und Lösungen erarbeitet werden. Ein Beispiel sind Erds-Szekeres Fragen. Um 1933 stellte Klein die Frage, ob es für jede natürliche Zahl k eine natürliche Zahl g(k) gibt sodaß jede Menge von g(k) Punkten in der Ebene in allgemeiner Lage ein konvexes k-Eck beinhaltet. Ausgehend von dieser Frage und Ihrer positiven Beantwortung durch Erds und Szekeres hat sich eine Klasse von Fragestellungen über die Existenz und Anzahl von Vielecken in Punktmengen entwickelt, die als Erds-Szekeres Fragen bekannt sind. Wir konnten mehrere solcher Fragestellungen beantworten. Besonders hervorzuheben ist die erste überlineare untere Schranke für die Anzahl von Fünfecken ohne innere Punkte, womit eine über dreißig Jahre alte Vermutung bestätigt werden konnte. Ein zweites Beispiel ist das Problem der Zerlegung einer geradlinigen Zeichnung eines Graphen - die viele Kreuzungen enthalten kann - in möglichst wenige kreuzungsfreien Teilzeichnungen. Das entsprechende Berechnungsproblem war Thema der Computational Geometry Challenge (CG:SHOP 2022) im Zuge des 38th International Symposium on Computational Geometry (SoCG 2022), der Spitzenkonferenz des Forschungsgebiets. Für vollständige Graphen auf 2n Knoten war eine alte Vermutung, dass diese immer in n kreuzungsfreie Spannbäume zerlegt werden können. In einer Zusammenarbeit zwischen drei Gruppen des Projekts ist es uns gelungen, diese Vermutung zu widerlegen und zu zeigen, dass nicht einmal eine Zerlegung in n beliebige kreuzungsfreie Teilzeichnungen immer möglich ist. Insgesamt hat das österreichische Team im Rahmen des Projekts zu 37 Publikationen in internationalen begutachteten, kompetitiven Konferenzen und Zeitschriften wesentlich beigetragen, wobei zusätzlich eine davon mit einem Best-Paper-Preis ausgezeichnet wurde, sechs zu einer Journalausgabe mit besonderen Beiträgen einer Konferenz ausgewählt wurden und eine den Preis der besten Konferenzpräsentation erhalten hat. Die Forschung, die durch dieses Projekt ermöglicht wurde war nicht nur sehr erfolgreich, sondern auch begeisternd und freudvoll. Wir beabsichtigen, diese Zusammenarbeit in der Zukunft fortzuführen.