Some Theoretical Perspectives on Recent Challenges in Graph Drawing

Abstract

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.

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.