GPU-basierte Graphenvisualisierung

Abstract

Visuellen Repräsentationen von Graphen begegnet man an vielen Stellen des Alltags, aber auch in der Wissenschaft und der Industrie. Diese basieren auf abstrakten Daten, die entweder implizit bei der Erstellung der Grafik entstanden sind oder die explizit aus einer Datenbank entnommen wurden, um sie durch eine schematische Zeichnung zugänglicher zu machen. Das Themengebiet des Graph-Drawings beschäftigt mit der Problematik, aus diesen abstrakten Daten eine visuelle Repräsentation zu schaffen. Eine Art der Darstellung ist die des Node-Link-Diagramms, in dem Knoten als positionierte Knotenpunkte und Kanten als Verbindungen zwischen diesen visualisiert werden. Ein wichtiger Aspekt dabei ist die Bestimmung eines Knotenlayouts. Je nachdem, wo die Knoten gesetzt werden, lassen sich Eigenschaften der darunterliegenden Daten erkennen. Dies ruft die Notwendigkeit von Layout-Verfahren auf den Plan. Dabei gibt es verschiedene Ansätze, die ein Optimierungsproblem definieren und anschließend numerisch anwenden, da für nicht-triviale Problemgrößen eine direkte Lösung problematisch ist. So werden zum Beispiel Knoten elektrisch geladen und Kanten als Federn zwischen den Knoten modelliert oder es wird eine Übersetzung in ein algebraisches Problem vorgenommen, für das es bereits Lösungen gibt. Im Zusammenhang der Problemgröße bietet es sich durch neue Entwicklungen in der Grafikhardware an, aufwändige Berechnungen durch die gebotene Parallelität auf der GPU zu beschleunigen. Es gibt dafür bereits einige Konzepte, die durch die damals aktuellen Schnittstellen nicht direkt, sondern nur durch umständliche Umwege umgesetzt werden konnten. Neben dem Knotenlayout stellen sich weitere Fragen im Zusammenhang mit der Visualisierung von Graphen als Node-Link-Diagramme. Diese fließen zusammen in das Konzept eines Frameworks ein, das ein generelles Vorgehen präsentiert und dabei auf die Verwendung der Grafikhardware eingeht. Dazu gehört neben der Einbettung der Layout-Verfahren auch die Wahl passender Visualisierungen für Knoten und Kanten, aber auch eine Auseinandersetzung mit Interaktionskonzepten. Eine Implementierung dieses Frameworks bietet weitere Aufschlüsse über die konzipierten Strukturen und Zusammenhänge und die Möglichkeit der Evaluation bezüglich Speicher- und Laufzeitverhalten.