Geordnete Graphenzerlegungen und ihre Anwendungen

• Antragstellerin: Dr. Lena Marie Schlipf
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 512370152

Algorithmische Graphentheorie ist ein wichtiges und umfangreiches Forschungsgebiet. Viele Probleme aus dem realen Leben können als graphentheoretische Probleme modelliert werden, z. B. Routenplanung, Entwurf von Kommunikationsnetzwerken und VLSI-Design. Schon seit Jahrzehnten werden geordnete Graphenzerlegungen als zentrales Werkzeug in der algorithmischen Graphentheorie verwendet. Diese Ordnungen zerlegen den Graphen in Teilgraphen, die bestimmte Kriterien wie (Kanten-)Zusammenhang erfüllen. Beispiele hierfür sind st-Nummerierungen und kanonische Ordnungen. Eng verwandt mit geordneten Graphenzerlegungen sind induktiv definierte Konstruktionen von Graphklassen, da viele Algorithmen, die geordnete Graphenzerlegungen berechnen, auf induktiv definierten Konstruktionen beruhen. Eine gute Kenntnis dieser Konzepte ist sehr hilfreich, um Probleme in der Algorihmischen Graphentherie zu lösen; neue Erkenntnisse über diese Konzepte können auch hilfreich sein, um langjährige offene Probleme zu lösen (z.B. die Vermutung der kantenunabhängigen Spannbäume). Das Hauptziel dieses Projekts ist es, geordnete Graphenzerlegungen und induktiv definierte Konstruktionen von Graphen zu untersuchen, neue zu entwickeln und ihre Relevanz an unterschiedlichen Anwendungsbeispielen zu verdeutlichen. (1.) Wir untersuchen verschiedene Konzepte von Graphenzerlegungen und induktiv definierten Konstruktionen. Beispielsweise sind wir an (Kanten-)Ordnungen für k-(kanten-)zusammenhängende Graphen mit k größer als vier interessiert. Darüber hinaus planen wir, eingeschränkte Graphenklassen, wie z.B. 1-planare Graphen und deren Unterklassen, als Anwendungsfälle zu untersuchen. Wir erhoffen uns, dass wir nicht nur neue Konzepte finden (die nicht nur für sich alleine schon spannend sind), sondern dass diese auch benutzt werden können um eine Vielzahl an Problemen zu lösen (siehe (2.)). (2.) Wir wollen die Mächtigkeit von (unseren neu entwickelten) geordneten Graphenzerlegungen und induktiv definierten Konstruktionen veranschaulichen. Dafür betrachten wir Laman-Graphen und untersuchen einige langjährig offene Probleme in der Graphentheorie. Zusätzlich werden wir unsere neu entwickelten Graphenzerlegungen an spannenden Problemen im Graphenzeichnen anwenden, z.B. auf Sichtbarkeitsdarstellungen.

• DFG-Verfahren: Sachbeihilfen