Bachelor Thesis BCLR-0072

BibliographyPfannkuch, Tilo: GPU-basierte Graphenvisualisierung.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 72 (2013).
74 pages, german.
CR-SchemaE.1 (Data Structures)
I.3.1 (Computer Graphics Hardware Architecture)
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.

Full text and
other links
PDF (6963961 Bytes)
Department(s)University of Stuttgart, Institute of Visualisation and Interactive Systems, Visualisation and Interactive Systems
Superviser(s)Panagiotidis, Alexanros; Reina, Guido
Entry dateNovember 14, 2013
New Report   New Article   New Monograph   Computer Science