Inhaltszusammenfassung:
Graphenzeichnen stellt essenzielle Methoden zur Verf¨ugung, um komplexe und
umfangreiche Systeme zu visualisieren. Dies erm¨oglicht dem Menschen, Dinge
zu sehen, zu lernen und zu verstehen, die ansonsten ungesehen, ungelernt und
unverstanden blieben. Da zunehmend neue Anwendungsbereiche entstehen, von
phylogenetischen B¨aumen, die in der Biologie die Evolutionsgeschichte allen
Lebens darstellen, bis hin zu Flussdiagrammen, die in Schulen, Universit¨aten und
in Unternehmen weltweit Abl¨aufe aller Art visualisieren, ist es nicht ¨uberraschend,
dass sich uns laufend neue Herausforderungen stellen. In dieser Arbeit werden
wir drei dieser aktuellen Herausforderungen aus der praktischen Anwendung
untersuchen, sie in einen theoretischen Kontext stellen und anwendbare L¨osungen
bieten.
Das erste Problem behandelt die Darstellung von zweistufigen Graphen, deren
Knotenmenge aus zwei disjunkten Teilen besteht. ¨ Ublicherweise werden zweistufige
Graphen mithilfe von 2-Layer-Zeichnungen dargestellt, bei denen jeder der
zwei Teile auf einer eigenen horizontalen Linie gezeichnet wird. Abgesehen von
ausgesprochen kleinen Graphen passt die Darstellung in aller Regel nicht auf
einen einzigen Computerbildschirm. Dies ist zwar unvermeidlich, allerdings
k¨onnen wir versuchen sicherzustellen, dass jeder Knoten mit all seinen Nachbarknoten
vollst¨andig auf einen einzigen Bildschirm passt. Diese Aufgabenstellung
bezeichnen wir als das Window Width Problem, von dem wir mehrere Varianten
untersuchen werden. Dabei sollen die Knoten so angeordnet werden, dass die
Bedingung auch f¨ur einen kleinstm¨oglichen Bildschirm erf¨ullt ist. Wir beweisen,
dass eine Variante des Problems in Polynomialzeit l¨osbar ist, w¨ahrend eine andere
Variante NP-schwer ist. Außerdem wird ein Approximationsalgorithmus f¨ur die
zweite Variante entwickelt und relaxierte Probleme untersucht. Dar¨uber hinaus
werden einige Experimente durchgef¨uhrt, um den praktischen Wirkungsgrad der
implementierten Algorithmen zu bewerten.
Das zweite Problem widmet sich der gleichzeitigen Darstellung mehrerer hierarchischer
Strukturen. Insbesondere untersuchen wir die gleichzeitige Einbettung
von mehreren B¨aumen, bei denen die Visualisierung eine bestimmte Reihenfolge
der Blattpunkte erfordert. Eine solche Bedingung ist f¨ur viele Anwendungen
n¨utzlich, da sie es erm¨oglicht, die Datenpunkte sortiert darzustellen, zum Beispiel
alphabetisch, um ein effizientes Auffinden zu bewirken. Konkret werden k verwurzelte,
gestufte B¨aume vorgegeben, deren Bl¨atter sich alle auf derselben Ebene
befinden, und zwar in einer geforderten Reihenfolge. Das Problem besteht darin,
Ordnungen f¨ur die Knoten aller anderen Stufen zu finden, sodass die Gesamtzahl
der Kreuzungen minimal ist. Es ist zwar bekannt, dass dieses Problem f¨ur beliebig
viele B¨aume auch auf nur zwei Stufen NP-schwer ist, aber wir liefern einen FPL-Algorithmus in k, f¨ur den Fall mit zwei Stufen und einen XP-Algorithmus
in k f¨ur den Fall mit drei Stufen. F¨ur beliebig viele Schichten zeigen wir, dass
das Problem in Polynomialzeit l¨osbar ist, wenn man die Anzahl der B¨aume auf
zwei beschr¨ankt.
Das dritte Problem behandelt dynamische Visualisierungen. W¨ahrend statische
Darstellungen f¨ur technische und analoge Anwendungen noch immer relevant
sind, nutzt die breite ¨Offentlichkeit zunehmend interaktive Visualisierungen.
Daher ist es notwendig, bekannte Zeichenmethoden f¨ur dynamische Aufgaben
nutzbar zu machen. Konkret betrachten wir ortho-radiale Metrokarten. Diese
Abbildungen ¨offentlicher Verkehrsnetze zeigen die Verkehrslinien entlang konzentrischer
Kreise und auf Linien, die vom Mittelpunkt ausgehen. Wir passen das
Zeichnungsmodell so an, dass es sich f¨ur dynamische Anwendungen eignet, und
schlagen konkrete Zeichenstrategien vor, die f¨ur kontinuierlich aktualisierende
und f¨ur geor¨aumliche Netzwerke nutzbar sind. Dar¨uber hinaus stellen wir ein
hybrides Visualisierungsmodell vor, das lokal exakte und global schematische
Darstellungen kombiniert.
Zuletzt widmen wir uns knapp f¨unf weiteren aktuellen Herausforderungen, f¨ur
welche wir gut lesbare Visualisierungen pr¨asentieren, bevor wir die Arbeit mit
einigen interessanten offenen Forschungsproblemen abschließen.
Abstract:
Graph Drawing provides essential tools to visualize complex and extensive systems.
In doing so it allows humans to see, learn and understand what would
otherwise remain unseen, unlearned and incomprehensible. As new areas of
application arise regularly, ranging from phylogenetic trees, displaying the evolutionary
history of all life on earth in biology, to flowcharts, visually representing
processes of virtually everything in schools, universities and business offices all
over the world, it is unsurprising that new challenges emerge constantly. In
this thesis we will investigate three recent challenges emanating from practical
applications, bringing them into the theoretical context and provide applicable
solutions.
The first problem concerns the representation of bipartite graphs whose vertex
set consists of two disjoint parts. Commonly bipartite graphs are displayed using
2-layer drawings, where each part is drawn on a distinct horizontal line. However,
unless the graph is relatively small, the representation does not fit on a single
computer screen. While this is inevitable, we would like to make sure one vertex
with all its neighbors still fits on a single screen. Typically the two parts of the
vertex set play considerably different roles in the data set, which leads to different
variants of the problem. This introduces the so-called Window Width problem,
where vertices are rearranged such that the smallest screen possible suffices.
We prove that one variant of the problem is polynomial time solvable, while
another one is NP-hard. Additionally, we provide an approximation algorithm
for the second variant and study relaxed problems. Further, some experiments
are performed, evaluating the practical impact of the implemented algorithms.
The second problem considers the display of multiple hierarchical structures at
once. Particularly, we investigate into the simultaneous embedding of multiple
trees, where the visualization requires a specific order of the leaf vertices. Such a
requirement is useful for many application, as it allows to show the data points
sorted, for instance alphabetically, to enable efficient lookup. Specifically, k
rooted, layered trees are provided whose leaves are all placed on the same layer,
in a required total order. The problem consists of finding orders for the vertices
of all other layers, such that the total number of crossings is minimal. While it
is known that this problem is NP-hard for arbitrarily many trees even on only
two layers, we provide an FPL-algorithm in k if the number of layers is two,
and an XP-algorithm in k if the number of layers is three. For arbitrarily many
layers we show that the problem is polynomial time solvable when restricting
the number of trees to two.
The third problem considers dynamic visualizations. While static visualizations
are still relevant for technical and analogue applications, the general public increasingly uses interactive visualizations. Thus, it is necessary to make known
drawing methods applicable for dynamic tasks. Specifically we consider orthoradial
metro maps. These representations of public transportation networks
show the lines of transportation along concentric circles and on lines emanating
from the center point. We extend the drawing model to be suitable for dynamic
applications, proposing drawing strategies which are applicable for continuously
updating and geospatially augmented data. Further we introduce a hybrid visualization
model combining locally precise and globally schematic representations.
Finally, we briefly discuss five other recent challenges for which we provide
well-readable visualizations, before concluding the thesis with some interesting
open research problems.
Layered Graphs