Graphvisualisierung und Evolutionäre Algorithmen - Eine Theoretische Perspektive

• Antragsteller: Professor Dr. Ignaz Rutter; Professor Dr. Dirk Sudholt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 577782724

Graphen sind ein fundamentales Werkzeug im digitalen Zeitalter zur Modellierung von Beziehungen in Bereichen wie sozialen Netzwerken, Softwaresystemen und biologischen Daten. Eine effektive Visualisierung von Graphen hilft Nutzern dabei, komplexe Strukturen zu interpretieren. Das Forschungsfeld Graph Drawing (Graphvisualisierung) entwickelt Algorithmen zur Berechnung solcher Layouts. Wichtige ästhetische Kriterien sind dabei die Minimierung von Kreuzungen, die Optimierung von Winkeln sowie eine kompakte Darstellung. Diese Ziele stehen oft im Widerspruch zueinander, was die Layout-Erzeugung zu einem multikriteriellen und meist NP-schweren Optimerungsproblem macht. Evolutionäre Algorithmen (EAs) sind leistungsfähige, populationsbasierte Metaheuristiken, die von den Prinzipien der natürlichen Evolution inspiriert sind. Sie sind vielseitig, anpassungsfähig, und ideal für multikriterielle Optimierung, da Populationen auf natürliche Weise Kompromisse zwischen konkurrierenden Zielen speichern. EAs eignen sich zudem ideal für Probleme mit komplexer, unbekannter oder schwer modellierbarer Struktur. Trotz vielversprechender empirischer Ergebnisse im Bereich der Graphvisualisierung werden EAs bislang nur wenig eingesetzt, was vor allem an fehlenden theoretischen Grundlagen liegt. Dieses Projekt, eine enge Zusammenarbeit von Experten für Graphvisualisierung und Theorie evolutionärer Algorithmen, zielt darauf ab, die Lücke zwischen diesen beiden Forschungsfeldern zu schließen. Wir wenden rigorose Laufzeitanalysen an, um bewiesene Garantien für die Zeit abzuleiten, die EAs benötigen, um hochwertige Graphlayouts zu erzeugen. Dies ermöglicht allgemeine, mathematisch fundierte Aussagen und unterstützt die systematische Entwicklung effektiver Algorithmen. Unser Fokus liegt auf Zeichenstilen mit strukturierten, aber komplexen Lösungsräumen, wie z.B. hierarchischen Darstellungen, bei denen Graphen auf horizontalen Ebenen mit nach oben gerichteten Kanten gezeichnet werden. Aus Sicht der Graphvisualisierung wollen wir verstehen, wie sich Designentscheidungen bei EAs - etwa die Wahl von Operatoren (z.B. Mutation und Crossover) und Parametern (z.B. Populationsgröße) - auf die Layoutqualität auswirken. Dieses Verständnis wird die Entwicklung von EAs ermöglichen, die konzeptionell einfach sind und gleichzeitig nachweisbare Leistungsgarantien bieten. Die Algorithmen werden speziell für Aufgaben der Graphvisualisierung angepasst und in der Lage sein, vielfältige, qualitativ hochwertige Layouts zu erzeugen - mit hoher Robustheit und kreativer Flexibilität. Aus Sicht der EA-Theorie stellt die Graphvisualisierung neuartige Herausforderungen dar, die zur Entwicklung besserer Analysewerkzeuge und Operatorendesigns führen werden. Die Machbarkeit und Bedeutung dieses Forschungsvorhabens werden durch die vorbereitenden Arbeiten der Antragsteller unterstrichen, die mit einem Best Paper Award auf der Leitkonferenz der ACM für evolutionäre Algorithmen ausgezeichnet wurden.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: USA
• Kooperationspartner: Professor Dr. Andrew M. Sutton