Gefördert durch die Deutsche Forschungsgemeinschaft (DFG), Projektnummer 577782724 ab Juni 2026
Dieses Projekt erarbeitet eine rigorose theoretische Grundlage an der Schnittstelle von Graphvisualisierung und Evolutionären Algorithmen (EAs). EAs sind eine leistungsstarke und vielseitige Familie von Optimierungsverfahren, die von der biologischen Evolution inspiriert sind und seit über 35 Jahren erfolgreich auf eine Vielzahl von Graphvisualisierungsproblemen angewendet werden. Indem dieser praktische Erfolg mit den analytischen Methoden der Laufzeitanalyse verbunden wird, leiten wir nachweisbare Leistungsgarantien für EA-basierte Algorithmen zur Graphvisualisierung her und vereinen so konzeptionelle Einfachheit mit mathematischer Genauigkeit und Vorhersagekraft.
Der Schwerpunkt liegt auf lagenbasierten Graphzeichnungen und dem weit verbreiteten Sugiyama-Framework, wobei zentrale Probleme wie Kreuzungsminimierung, Kreisbeseitigung und Lagenzuweisung untersucht werden. Darüber hinaus werden weitere Zeichenstile wie Kreiszeichnungen und Bucheinbettungen betrachtet. Aus Sicht der EA-Theorie bietet die Graphvisualisierung eine reichhaltige Klasse von Optimierungsproblemen, die über klassische Darstellungen hinausgehen und neue Herausforderungen und Chancen für die Weiterentwicklung des Gebiets eröffnen.
Das Projekt ist eine enge Kooperation zwischen dem Lehrstuhl für Theoretische Informatik (PI: Ignaz Rutter) und dem Lehrstuhl für Algorithmen für Intelligente Systeme (PI: Dirk Sudholt), beide an der Universität Passau.
Gefördert durch die Deutsche Forschungsgemeinschaft (DFG), ab Oktober 2024
Die Netzwerkvisualisierung beschäftigt sich mit der Berechnung geometrischer Darstellungen von Graphen, die das menschliche Verständnis unterstützen. Ein zentrales Konzept ist die Planarität: Ein Graph heißt planar, wenn er kreuzungsfrei gezeichnet werden kann. Planarität ist gut verstanden und bildet die Grundlage vieler effizienter Algorithmen in der Netzwerkvisualisierung.
In der Praxis sind die meisten realen Netzwerke jedoch nicht planar. Graphklassen jenseits von Planarität (engl. beyond-planar graphs) — wie 1-planare, k-planare, fan-planare, RAC- und quasi-planare Graphen — verallgemeinern Planarität, indem sie Kreuzungen zulassen, aber deren Auftreten einschränken (z. B. darf jede Kante höchstens einmal gekreuzt werden, oder alle Kreuzungen müssen rechtwinklig sein). Während die kombinatorischen Eigenschaften dieser Klassen zunehmend gut verstanden sind, sind ihre algorithmischen Grundlagen weitgehend unerforscht: Für fast alle relevanten beyond-planaren Graphklassen ist bereits die Entscheidung, ob ein gegebener Graph zur Klasse gehört, NP-schwer, und praktisch einsetzbare Algorithmen fehlen weitgehend.
Das Ziel dieses Projekts ist die Entwicklung eines algorithmischen Werkzeugkastens zur Erkennung, Einbettung und Zeichnung beyond-planarer Graphen. Wir verfolgen dies entlang von vier Forschungslinien: parametrisierte und Approximationsalgorithmen zur Erkennung, exakte und heuristische Algorithmen für den praktischen Einsatz, geometrische und typologische Realisierbarkeit von Kreuzungsstrukturen sowie Beyond-Planarität für gerichtete Graphen. Das Projekt wird in Zusammenarbeit mit Partnern an den Universitäten Tübingen, Trier, Roma Tre, TU Wien, Perugia und Utrecht durchgeführt.
(DFG/GAČR, Oktober 2019 – November 2023, mit Alexander Wolff, Univ. Würzburg, und Jiří Fiala, Charles-Univ. Prag)
Graphen und Netzwerke lassen sich geometrisch repräsentieren, indem man den Knoten geometrische Objekte — etwa Intervalle, Kreise oder komplexere Formen — zuordnet und Kanten durch Schnitte oder gegenseitige Sichtbarkeit dieser Objekte kodiert. Solche Repräsentationen treten in vielen Anwendungsgebieten auf und sind ein zentrales Thema in der diskreten Mathematik und der theoretischen Informatik.
Dieses Projekt untersucht algorithmische und kombinatorische Eigenschaften verschiedener Familien geometrischer Repräsentationen. Die Forschungsrichtungen umfassen: die Erweiterung einer gegebenen partiellen Repräsentation zu einer vollständigen; die Konstruktion simultaner, kompatibler Repräsentationen für mehrere verwandte Graphen; die Minimierung der Anzahl von Hindernissen in Sichtbarkeitsrepräsentationen; die Analyse H-topologischer Schnittgraphen als parametrische Verallgemeinerung von Intervallgraphen; die Berechnung bzw. Approximation der maximalen Anzahl von Kantenkreuzungen in geradlinigen Zeichnungen; sowie die Charakterisierung von Graphen, die Zeichnungen mit kleiner Ply-Zahl erlauben.
