Zeichen-Algorithmen für Beyond-Planare Graphen

• Antragsteller: Professor Dr. Ignaz Rutter
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 541433306

Planare Graphen, d.h. Graphen, die sich ohne Kreuzungen in die Ebene zeichnen lassen, sind ein wichtige Kernelement vieler Techniken in der Graphvisualisierung. Im Gegensatz dazu sind viele in der Praxis auftretende Graphen nicht planar. Sie sind jedoch zumeist dünn besetzt und "annähernd planar", im Sinne dessen, dass sie eine Zeichnung besitzen, in der die Kreuzungen günstig verteilt sind. Um die direkte Anwendbarkeit auf Echtwelt-Instanzen zu erhöhen und die durch die zentrale Rolle der Planarität bedingten Beschränkungen zu überwinden, wurde im Feld des Graphenzeichnens die Untersuchung sogenannter beyond-planar graphs begonnen. Dabei handelt es sich um Graphen, die zwar nicht planbar sind, jedoch in gewissem Sinne "nahe dran" sind. Ein Beispiel sind 1-planare Graphen, welche eine Zeichnung besitzen, in der jede Kante höchstens eine Kreuzung besitzt. Inzwischen ist eine ganze Reihe von beyond-planaren Graphklassen bekannt, und diese wurden intensiv untersucht. Eine große Menge an Literatur beantwortet viele Schlüsselfragen, etwa die Bestimmung der maximalen Dichte und auch den Vergleich verschiedener beyond-planarer Graphklassen. Ein wesentliches Hemmnis beim Transfer dieser Resultate in praktische Anwendungen ist die Tatsache, dass für nahezu alle relevanten beyond-planaren Graphklassen die Komplexität des entsprechenden Erkennungsproblems entweder offen ist, oder sich als NP-vollständig herausgestellt hat. Fortschritte in diesem Bereich beschränken sich bisher auf polynomielle Algorithmen für Spezialfälle. Das Ziel dieses Projekts ist die Entwicklung einer algorithmischen Toolbox um mit beyond-planaren Graphen zu arbeiten. Zu diesem Zweck werden wir beyond-planare Graphen mit einem starken algorithmischen Schwerpunkt auf Erkennungs- und Zeichenproblemen untersuchen. Um die bekannten Schwereresultate zu überwinden, werden wir eine Reihe von algorithmischen Techniken einsetzen, beginnend bei Approximations- und parametrisierten Algorithmen bis hin zu exakten und heuristischen Ansätzen.

• DFG-Verfahren: Sachbeihilfen