Algorithmen für die Interaktion im Graphenzeichnen

• Antragstellerin: Professorin Dr. Dorothea Wagner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 244429338

In der Vergangenheit wurden Computer vor allem als Werkzeug genutzt um "einen Job zu erledigen". Erst die technologischen Entwicklungen der letzten Jahre lassen uns Computer zunehmend als Assistenten ansehen, die in interaktiver Kooperation zur Bearbeitung einer Aufgabe eingesetzt werden. Entsprechend verschiebt sich auch im Graphenzeichnen der Fokus von automatischen Layoutalgorithmen zu einer verstärkt interaktiven Vorgehensweise, bei der Zeichnungen in einem iterativen Prozess und in Interaktion zwischen Benutzer und System erstellt werden.In diesem Projekt wollen wir uns Methoden zur Interaktion mit Graphenlayouts widmen. Zur Zeit klafft eine deutliche Lücke zwischen den existierenden einfachen Operationen zur Interaktion mit Graphenlayouts und vollautomatischen Layoutalgorithmen. Elementare Interaktionstechniken wie das Verschieben von Knoten, Rotation oder Skalierung erlauben dem Nutzer eine genaue Kontrolle des Layoutprozesses, sind aber für große Änderungen des Layouts ungeeignet. Andererseits stehen Graphenzeichnenalgorithmen zur Verfügung, die die automatische Erstellung von Layouts unter Einhaltung vorgegebener (gegebenenfalls interaktiv spezifizierter) Layoutbedingungen ermöglichen (constrained graph drawing). Dieser Ansatz erlaubt umfangreiche Änderungen des Layouts und ist auch für große Graphen anwendbar,zumindest wenn effiziente Algorithmen zur Verfügung stehen. Allerdings bietet er nur sehr eingeschränkte Kontrolle über den Layoutprozess (es sei denn die Anzahl an spezifizierten Layoutbedingungen ist groß).Unser Ziel ist es die Lücke zwischen diesen Extremen zu schließen. Im Rahmen dieses Projekts wollen wir einerseits neue Layoutalgorithmen entwickeln, die dem Nutzer die Formulierung von Layoutbedingungen erlauben, etwa an die Position von Teilmengen der Knotenmenge oder an die Kurvenkomplexität wichtiger Kanten. Andererseits wollen wir die Mächtigkeit manueller Interaktion erhöhen indem wir komplexere Operationen einführen, die leicht benutzbar und gleichzeitig mächtig genug sind um umfangreiche Layoutmanipulationen in nur wenigen Modifikationsschritten zu ermöglichen. Zu diesem Zweck entwerfen wir neue Algorithmen, die den Benutzer bei der Manipulation von Graphenlayouts unterstützen indem sie das Layout kontinuierlich entsprechend den Eingaben des Nutzers aktualisieren. Für die Verfeinerung derartiger Operationen und um ihre Anwendungbarkeit auf große Graphen zu ermöglichen werden wir Methoden entwerfen, die geeignet kleine Abstraktionen vonGraphen generieren. Diese Abstraktionen sollen für die Interaktion genutzt werden und mittels neuer Verfahren, die die Layoutänderungen an einer Graphenabstraktion kontinuierlich extrapolieren, soll daraus wieder das endgültige Layout des Ausgangsgraphen entstehen.

• DFG-Verfahren: Sachbeihilfen