Produkt-Struktur von Graphen

• Antragsteller: Privatdozent Dr. Torsten Ueckerdt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 532213793

Der Produktstruktursatz für planare Graphen ist eine Möglichkeit, planare Graphen in Form von Graphen mit einer einfacheren Struktur auszudrücken, und zwar auf eine Weise, die sich für strukturelle und algorithmische Anwendungen als nützlich erweist. Gemeinsam mit unseren Koautoren haben wir dieses Theorem kürzlich bewiesen, aufbauend auf den Pionierarbeiten von Pilipczuk und Siebertz. Es besagt, dass jeder planare Graph ein Untergraph des starken Produkts aus einem Graphen der Baumweite 8 und einem Pfad ist. Das Produktstrukturtheorem für planare Graphen hat in kürzester Zeit bereits eine Reihe wichtiger Anwendungen in der Kombinatorik und der theoretischen Informatik gefunden. Es ist zu erwarten, dass in naher Zukunft noch mehr davon gefunden werden. Dieses neue Werkzeug könnte in der Tat der Schlüssel zu Fortschritten bei einer Reihe von offenen Problemen im Zusammenhang mit planaren Graphen sein. In diesem Projektantrag listen wir einige Richtungen auf, von denen wir glauben, dass sie in dieser Hinsicht Potenzial haben. Neben der Suche nach neuen Anwendungen glauben wir, dass es Untersuchungen wert ist, die Theorie zu verbessern und weiter zu entwickeln. Erstens sind die derzeitigen Schranken höchstwahrscheinlich nicht scharf, so dass es noch Raum für Verbesserungen gibt. Zweitens wäre es sehr interessant, neue interessante Graphenklassen zu identifizieren, die eine Form des Produktstruktursatzes erfüllen. Im Moment sind außer planaren Graphen nur eine Handvoll Beispiele bekannt. Nicht zuletzt möchten wir die Synergie der drei Antragsteller und ihrer jeweiligen Teams nutzen, um einige seit langem bestehende Herausforderungen in der strukturellen Graphentheorie in Angriff zu nehmen. Unser Schwerpunkt liegt dabei auf der bestmöglichen oberen Schranke des berühmten Grid-Minor-Theorems von Robertson und Seymour, einem der Eckpfeiler der Graph-Minoren-Theorie mit unzähligen Anwendungen. Dies ist zweifellos ein ehrgeiziges (und riskantes) Ziel.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Belgien, Polen
• Partnerorganisation: Fonds National de la Recherche Scientifique - FNRS; Narodowe Centrum Nauki (NCN)
• Kooperationspartner: Professor Gwenaël Joret, Ph.D.; Professor Piotr Micek, Ph.D.