Elastic set visualization : Hypergraph visualization with moving objects and fat edges

Abstract

Die Visualisierung von Hypergraphen ist äquivalent zur Visualisierung von Sets, da die Knoten eines Hypergraph als Setelemente und die Hyperedges als Sets interpretiert werden können. Daher ist die Visualisierung dieser Strukturen ein wichtiges Thema sowohl in der Graphendarstellung als auch in der Informationsvisualisierung. Bei einigen Hypergraphen kann die Zuordnung von Knoten im Graphen zu Positionen in der Visualisierung nicht beliebig gewählt werden (beispielsweise bei der Visualisierung von geographischen Daten auf einer Karte). Die Visualisierung solcher Hypergraphen mit einer existierenden Knotenzuordnung ist ein aktives Forschungsgebiet, für das in den letzten Jahren mehrere verschiedene Methoden entwickelt worden sind. Diese bestehenden Visualisierungsmethoden sind im Allgemeinen für eine statische Knotenzuordnung entwickelt worden. In der Praxis ist es jedoch möglich, dass sich diese Knotenzuordnung im Laufer der Zeit ändert oder auf Benutzereingaben reagieren muss. Ein Beispiel dafür wäre die Visualisierung von Flugzeugen auf einer Karte, bei der die Flugzeuge durch Knoten dargestellt werden und die Hyperedges die Zugehörigkeit zu einer Fluggesellschaft darstellen. In dieser Arbeit schlagen wir eine Technik vor, die die Grundlage für eine solche Hypergraph-Visualisierung bildet. Diese Technik ist inspiriert von State of the Art Hypergraph-Visualisierungstechniken und anderen Konzepten der Graphendarstellung, um Hypergraphen nicht nur in einer statischen Umgebung zu visualisieren, sondern auch mit zeitlich veränderlichen Daten umgehen zu können. Zu diesem Zweck entwickeln und implementieren wir neue Algorithmen, um diese Art der Visualisierung zu konstruieren. Darüber hinaus führen wir Qualitätsmetriken für die Visualisierung ein und verwenden diese Metriken, um die von den implementierten Algorithmen erzeugten Visualisierungen zu bewerten.

Visualizing hypergraphs is equivalent to visualizing sets, since the vertices of a hypergraph can be interpreted as set items and the hyperedges as sets. Therefore, visualizing these structures is a prominent topic in both graph drawing and information visualization. For some hypergraphs, the mapping of vertices in the graph to positions in the visualization cannot be chosen arbitrarily (e.g. when visualizing geospatial data on a map). Visualizing such hypergraphs with a fixed vertex mapping is an active area of research for which several different methods have been developed in recent years. These existing visualization methods are generally designed with static vertex mappings in mind. However, in practice, it is possible that vertex mappings change over time or have to react to user input. An example of this would be a visualization of planes on a map, where the planes are represented by vertices and the hyperedges represent the membership to an airline. In this thesis, we propose a technique that builds the foundation to handle such a hypergraph visualization. It takes inspiration from state-of-the-art hypergraph visualizations and other graph drawing concepts to not only visualize hypergraphs in a static environment but is also adept at dealing with time-varying data. To that end, we develop and implement new algorithms to compute this type of visualization. We furthermore introduce quality metrics for the visualization and use those metrics to evaluate visualizations produced by the implemented algorithms.