Jenseits von Planarität: Eine Verallgemeinerung des Konzepts "Planarität" im Graphenzeichnen

• Antragsteller: Professor Michael Kaufmann, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 364468267

Das Forschungsgebiet der Graphen jenseits von Planarität hat sich in letzter Zeit drastisch entwickelt. Evidenz dafür sind verschiedene Workshops und Dagstuhl Seminare zu diesem Thema. Auch wird ein Überblicksbuch dazu in Kürze erscheinen. Im ersten Antrag von 2017 haben wir eine breite Sammlung von Forschungsfragen in verschiedene Richtungen zusammengestellt. Mittlerweile haben wir einiges dazu beigetragen, im Bericht haben wir unsere Aktivitäten zusammengefasst. Wir haben aber auch einige neue interessante Herausforderungen erkannt, die wir in den nächsten 3 Jahren bearbeiten wollen.1. Klassifikationen: Wir streben robuste Definitionen an, die auch parametrisierbar sind. Diese fehlen teilweise immer noch. Auch wollen wir klare Hierarchien zur besseren Einordnung der verschiedenen Graphklassen. Wir erwarten auch, neue Klassen zu finden, die das hierarchische Bild komplettieren. Die Klassifikation wird begleitet durch kombinatorische und algorithmische Analysesn der strukturelllen Eigenschaften und Parameter der zu betrachtenden Klassen.2. Layout: Während der ersten Projektphase haben wir gemerkt, dass insbesondere die Arbeit an Layoutalgorithmen für Graphen jenseits von Planarität sehr begrenzt ist. Der Hauptgrund dafür ist, dass die bekannten Techniken nicht so einfach übertragbar sind. Deshalb wollen wir für die zweite Phase unseren Fokus auf diesen Bereich legen. Beispielsweise sind beim etablierten Vorgehen, nämlich erst eine gute topologische Einbettung zu berechnen und daraus eine passende geometrische Repräsentation, beide Schritte für den vorliegenden Fall sehr anspruchsvoll und bringen eine gute Portion Risiko in das Projekt. Bisher sind nur elementare Resultate bekannt, die auch meist auf die Klasse von 1-planaren Graphen oder ganz eingeschränkte Teilszenarien beschränkt sind.3. Dissemination: In organisatorischer Hinsicht wollen wir dieses Gebiet auch weiter forcieren: Wir wollen weiter zu dem Thema Workshops mit anderen Gruppen veranstalten und besuchen (GNV in Heiligkreuztal, BWGD in Bertinoro, Dagstuhlseminare 2016, 2019, 2022 (geplant)). Diese Art der Forschungszusammenarbeit finden wir sehr effektiv, da sich Leute aus verschiedenen Gebieten (hier kombinatorische Graphentheorie, Graphenzeichnen, algorithmische Geometrie) treffen und produktiv zusammenarbeiten (siehe Publikationsliste). Außerdem wird unsere Gruppe in 2021 das 29. Symposium über Graphenzeichnen und Netzwerkvisualisierung in Tübingen organisieren, eine große Ehre und Anerkennung unserer bisherigen Arbeit.

• DFG-Verfahren: Sachbeihilfen