Graphen-Layout-Algorithmen für Graph-Visualisierung - Entwicklung einer generellen Struktur auf Basis von bestehenden Algorithmen

Die Analyse von Graphen und Netzwerken ist ein wichtiges Thema der diskreten Mathematik mit einer stetig wachsenden Anzahl von Anwendungsgebieten. Im Bereich Visual Analytics tauchen Graphen sowohl in der Darstellung von Daten (soziale Netzwerke, wirtschaftliche Beziehungen, Dokumentverbindungen, etc.), aber auch in der visuellen Darstellung abstrakter analytischer Modelle auf, wie etwa Entscheidungsbäume, probabilistische Netzwerke, etc. Technisch macht es aber keinen Unterschied, welche Graphen mit den Visualisierungstechniken angezeigt werden. Da die Wahl einer geeigneten Technik, aber durchaus von der konkreten Aufgabenstellung und der Art des Graphen abhängt, soll die Anpassung der Visualisierung an diese Aspekte in Zukunft möglichst effizient gestaltet werden. In der Vergangenheit war die Entwicklung der Visualisierungstechniken für Graphen und Hierarchien eher heterogen. Unterschiedliche Algorithmen für das Layout und die Abbildung visueller Strukturen wurden in unterschiedlichen Programmen und Zielsetzungen umgesetzt. In der vorliegenden Arbeit wurden diese Entwicklungen untersucht, und Software Design-Patterns identifiziert, die schließlich für die Entwicklung von einer "Standardvisualisierungtechnik" für Graphen notwendig sind. Besonders notwendig waren dabei die klare strukturelle Trennung der Algorithmen in Komponenten für das Zeichnen von Kanten und Knoten, das Layout des Graphen, die jeweils unabhängig voneinander ausgetauscht werden können. Besonderes Ziel dabei war auch, dass die zusätzliche Flexibilität keine spürbaren Einbußen an Performance mit sich bringt. Die Ergebnisse der Arbeit wurden in einem Prototypen, der alte Techniken in dem neuen Standard konsolidiert umgesetzt. Die Funktionalität dieses Prototypen wurde durch die unabhängige Rekombinierbarkeit verschiedener wesentlich erweitert.

The analysis of graphs and networks is an important topic in discrete mathematics. The number of application areas spans multiple fields of research. In the area of Visual Analytics graphs appear in both the representation of raw data models (such as social networks, economic relationships, citation networks, etc.) and the visual representation of abstract analytical models (decision trees, probabilistic networks, etc.). Technically any graph could be visualized with virtually any layout technique. However, the choice of a "good" visualization depends on aspects like task and graph type. Hence, the adaptation of a visualization technique to these aspects should be done more effectively. The development of visualization techniques for specific graphs and tasks resulted in a heterogeneous repertoire of source code for graph visualization. Different algorithms for the layout and the mapping of visual structures have been implemented in different architectures. In the thesis, older the source code of older techniques has been investigated for the identification of software design patterns that facilitate the development of a "standard" graph visualization technique. There is a need for a structural separation of different components for the drawing of edges and nodes and the layout of the graph. These components can be exchanged independently from each other. The increase in flexibility does not cause a significant increase of performance of the visualization. The results of the work have been implemented in a prototype, that consolidates old techniques in a new standard. The adaptability of the prototype to new graphs and applications has been increased by the independent recombination of its components.