Parameterized Graph Drawing

Dieses Projekt verbindet zwei prosperierende Themengebiete in der Informatik: Graphenzeichnen und Parametrisierte Komplexität. Graphenzeichen beschäftigt sich mit Entwurf und Analyse von grundlegenden Algorithmen zur Visualisierung von Graphen und Netzwerken, also der geometrischen Repräsentation von Knoten und Kanten. In der parametrisierten Komplexität hingegen werden Werkzeuge und Methoden zur Entwicklung von maßgeschneiderten effizienten Algorithmen erforscht, die strukturelle Eigenschaften von relevanten Eingaben als Parameter ausdrücken und diese im Algorithmenentwurf gezielt ausnutzen. In den letzten Jahren zeigte sich bereits das große Potenzial für die Anwendung und Entwicklung von neuen Methoden aus der parametrisierten Komplexität für schwierige algorithmische Probleme im Graphenzeichnen. Die beiden Projektleiter sind neben mehreren erfolgreichen gemeinsamen Vorarbeiten auch führend an einer laufenden Vernetzungsinitiative zwischen den beiden Themenbereichen beteiligt.

Dementsprechend liefert das beantragte Projekt einen wichtigen Beitrag um diese Bemühungen durch die eigene Forschung in den kommenden vier Jahren einen großen Schritt vorwärts zu bringen und viele prominente offene Fragen in diesem vielversprechenden Schnittbereich zu beantworten. Das Projekt ist dabei primär im Bereich der Grundlagenforschung angesiedelt, soll aber auch erste Schritte zum Transfer von parametrisierten Algorithmen aus der Theorie in die Praxis der Netzwerkvisualisierung beitragen.