Ply and Bar Visibility - Some Advanced Concepts in Graph Drawing

Abstract

Heutzutage sind Graphen als fundamentales mathematisches Modell zur Veranschaulichung von Relationen zwischen Objekten aus der Informatik nicht mehr wegzudenken. Ihre Anwendungen reichen von der Analyse sozialer Netzwerke über Routenplanung bis hin zu Interaktionsmodellen in der Biologie oder Chemie. Üblicherweise werden die Beziehungen zwischen den Objekten durch eine Zeichnung des Graphen veranschaulicht.

In dieser Arbeit wird die Ply-Zahl einer Zeichnung, welche als ästhetisches Kriterium vorgeschlagen wurde, untersucht. Gegeben sei eine gradlinige Zeichnung $\Gamma$ eines Graphen $G=(V,E)$ in der Ebene. Für jeden Knoten $v$ wird die Ply-Scheibe $D_v$ als Scheibe definiert, wobei das Zentrum der Scheibe auf dem Knoten $v$ liegt und der Radius $r$ von $D_v$ halb so lang ist, wie die längste inzidente Kante zu $v$. Die Ply-Zahl einer Zeichnung entspricht der maximalen Anzahl der sich überlappenden Ply-Scheiben in der Ebene. Zusätzlich beschreibt die maximale Anzahl an Scheiben, in denen sich ein Knoten befindet, die Knoten-Ply-Zahl.

Diese Arbeit beschäftigt sich mit theoretischen und praktischen Aspekten der Ply-Zahl von Zeichnungen. Es werden Eigenschaften von Zeichnungen präsentiert, die eine konstante Ply-Zahl haben. Zudem wird der Zusammenhang zwischen der Ply- und Knoten-Ply-Zahl einer Zeichnung untersucht.

Ein weiteres Kapitel widmet sich Graphen, welche Zeichnungen mit Knoten-Ply-Zahl 1 haben, sowie Graphen die keine Zeichnung mit Knoten-Ply-Zahl 1 haben. Insbesondere wird durch eine ausführliche Fallunterscheidung gezeigt, dass der vollständige Graph $K_8$, sowie der vollständig bipartite Graph $K_{3,15}$ nicht mit Knoten-Ply-Zahl 1 gezeichnet werden können.

Wir stellen ein Programm vor, dass es dem Nutzer ermöglicht ein intuitives Verständnis der Ply-Zahl als Parameter von geradlinigen Zeichnungen zu erlangen. Eine Zeichnung kann interaktiv modifiziert werden, was unter anderem auch für die theoretische Untersuchungen nutzbar ist.

Dazu präsentieren wir einen schnellen Algorithmus, der es ermöglicht zur Ply-Zahl sofortige Rückmeldung bei etwaiger Konfiguration der Zeichnung zu erhalten. Das war mit bisherigen Implementationen nicht möglich. Die Zeit zur Berechnung der Ply-Zahl für eine Zeichnung konnte von Sekunden auf Millisekunden verbessert werden. Das Programm beinhaltet zusätzlich verschiedene Layout-Mechanismen und die Möglichkeit die Ply-Zahl automatisiert zu optimieren. Mit verschiedenen Experimenten untersuchen wir die Layoutmethoden bezüglich der Ply-Zahl.

Neben der Ply-Zahl von geradlinigen Zeichnungen betrachten wir auch Bar Sichtbarkeitsrepräsentationen. In einer Bar $(k,j)$-Sichtbarkeitrepräsentation werden Knoten als horizontale Liniensegmente, genannt Bars, dargestellt und Kanten sind gegeben durch vertikale Segmente zwischen ihren inzidenten Knoten, sodass jede Kante höchstens $k$ Bars kreuzt und jeder Bar von höchstens $j$ Kanten gekreuzt wird.

In vorangehenden Publikationen wird der Begriff Bar $k$-Sichtbarkeit unterschiedlich verwendet. Wir geben die Möglichkeit diese Definitionen zu unterscheiden, und zwar in Bar $(1,\infty)$- und Bar $(1,1)$-Sichtbarkeitsrepräsentationen.

Zudem beschäftight sich diese Arbeit mit maximalen Bar $(1,j)$-Sichtbarkeits Graphen. Es kann eine Hierarchie dieser Graphklassen angegeben werden. D.h. für alle $j$ gibt es Graphen mit Bar $(1,j+1)$-Sichtbarkeitsrepräsentation, der keine Bar $(1,j)$-Sichtbarkeitsrepräsentation hat.

Des weiteren werden Bar $(k,1)$-Sichtbarkeitsrepräsentationen untersucht und wir können zeigen, dass es eingebettete Graphen mit Bar $(k,1)$-Sichtbarkeitsrepräsentation für ein $k >1$ gibt, welche aber keine Bar $(1,1)$-Sichtbarkeitsrepräsentation haben. Unsere Ergebnisse sind die ersten zu dieser Graph Klasse, welche eine Klasse von nicht-planaren Graphen mit wenigen Kanten ist.

Graphs are a fundamental mathematical model to represent relationships between objects and are used throughout a huge variety of disciplines in theory and practise. The use of graphs ranges in computer science from social network analysis to molecular interaction modelling in biology or chemistry. Accessing data from a graph very often involves a drawing of the graph. The ply-number has been defined as an parameter to evaluate the readability of a drawing.

Given a straight-line drawing $\Gamma$ of a graph $G=(V,E)$ in the plane, for every vertex $v$ the \plydisk $D_v$ is defined as a disk, centered in $v$, where the radius $r_v$ of $D_v$ is half the length of the longest edge incident to $v$. The maximum number of overlapping disks at any point in the plane defines the ply-number of the drawing and the maximum number of overlapping ply-disks at any vertex defines vertex-ply-number.

In this thesis, we present theoretical results on the ply-number and vertex-ply-number of drawings. We identify graphs, which have drawings with constant ply-number and evaluate the relationship between the ply-number and the vertex-ply-number in drawings.

To evaluate graphs that do or do not have empty-ply drawings, that is a drawing with vertex-ply-number 1, we present a comprehensive case distinction to show that the complete graph $K_8$ and the complete bipartite graph $K_{2,15}$ do not have empty-ply drawings.

We develop a supportive tool to give the user an intuitive understanding of the \plynumber of \straightline drawings. In particular, we present a fast algorithm to compute the \plynumber of a given drawing to enable instant feedback to the user, which was not possible with previous implementations . Furthermore, our tool is equipped with different layout methods and a workflow to optimize the \plynumber for a given graph.

We evaluate our algorithm to compute the ply-number and the optimization of drawings regarding this value with an extensive set of experiments. In fact, we were able to reduce the time to compute the \plynumber from seconds to milliseconds.

Beside the ply-number of straight-line drawings, we investigate bar-visibility representations of graphs. A bar $(k,j)$-visibility drawing of a graph $G$ is a drawing of $G$, where each vertex is drawn as a horizontal line segment, called bar, and each edge is drawn as a vertical line segment between its incident vertices such that each edge crosses at most $k$ bars and each bar is crossed at most $j$ times.

We clarify the differences between previous definitions on bar $k$-visibility representations, as they relate to bar $(1,\infty)$- or bar $(1,1)$-visibility representations.

In this thesis, we especially look at maximal bar $(1,j)$-visibility graphs and conclude a hierarchy of these graph classes. That is, there exist graphs, which have a bar $(1,j+1)$-visibility representation, but no bar $(1,j)$-visibility representation for every $j$. We investigate bar $(k,1)$-visibility representations and show that there exist embedded graphs that are bar $(k,1)$-visible but not bar $(1,1)$-visible for $k>1$. These are the first results on bar $(k,1)$-visibility drawings, which is a class of sparse graphs beyond planarity.