Graphs provide a key means to model relationships between entities. They consist of vertices representing the entities, and edges representing relationships between pairs of entities. To make people conceive the structure of a graph, it is almost inevitable to visualize the graph. We call such a visualization a graph drawing. Moreover, we have a straight-line graph drawing if each vertex is represented as a point (or a small geometric object, e.g., a rectangle) and each edge is represented as a line segment between its two vertices. A polyline is a very simple straight-line graph drawing, where the vertices form a sequence according to which the vertices are connected by edges. An example of a polyline in practice is a GPS trajectory. The underlying road network, in turn, can be modeled as a graph. This book addresses problems that arise when working with straight-line graph drawings and polylines. In particular, we study algorithms for recognizing certain graphs representable with line segments, for generating straight-line graph drawings, and for abstracting polylines. In the first part, we first examine, how and in which time we can decide whether a given graph is a stick graph, that is, whether its vertices can be represented as vertical and horizontal line segments on a diagonal line, which intersect if and only if there is an edge between them. We then consider the visual complexity of graphs. Specifically, we investigate, for certain classes of graphs, how many line segments are necessary for any straight-line graph drawing, and whether three (or more) different slopes of the line segments are sufficient to draw all edges. Last, we study the question, how to assign (ordered) colors to the vertices of a graph with both directed and undirected edges such that no neighboring vertices get the same color and colors are ascending along directed edges. Here, the special property of the considered graph is that the vertices can be represented as intervals that overlap if and only if there is an edge between them. The latter problem is motivated by an application in automated drawing of cable plans with vertical and horizontal line segments, which we cover in the second part. We describe an algorithm that gets the abstract description of a cable plan as input, and generates a drawing that takes into account the special properties of these cable plans, like plugs and groups of wires. We then experimentally evaluate the quality of the resulting drawings. In the third part, we study the problem of abstracting (or simplifying) a single polyline and a bundle of polylines. In this problem, the objective is to remove as many vertices as possible from the given polyline(s) while keeping each resulting polyline sufficiently similar to its original course (according to a given similarity measure). / Graphen stellen ein wichtiges Mittel dar, um Beziehungen zwischen Objekten zu modellieren. Sie bestehen aus Knoten, die die Objekte repräsentieren, und Kanten, die Beziehungen zwischen Paaren von Objekten abbilden. Um Menschen die Struktur eines Graphen zu vermitteln, ist es nahezu unumgänglich den Graphen zu visualisieren. Eine solche Visualisierung nennen wir Graphzeichnung. Eine Graphzeichnung ist geradlinig, wenn jeder Knoten als ein Punkt (oder ein kleines geometrisches Objekt, z. B. ein Rechteck) und jede Kante als eine Strecke zwischen ihren beiden Knoten dargestellt ist. Eine sehr einfache geradlinige Graphzeichnung, bei der alle Knoten eine Folge bilden, entlang der die Knoten durch Kanten verbunden sind, nennen wir Polylinie. Ein Beispiel für eine Polylinie in der Praxis ist eine GPS-Trajektorie. Das zugrundeliegende Straßennetzwerk wiederum kann als Graph repräsentiert werden. In diesem Buch befassen wir uns mit Fragen, die sich bei der Arbeit mit geradlinigen Graphzeichnungen und Polylinien stellen. Insbesondere untersuchen wir Algorithmen zum Erkennen von bestimmten mit Strecken darstellbaren Graphen, zum Generieren von geradlinigen Graphzeichnungen und zum Abstrahieren von Polylinien. Im ersten Teil schauen wir uns zunächst an, wie und in welcher Zeit wir entscheiden können, ob ein gegebener Graph ein Stickgraph ist, das heißt, ob sich seine Knoten als vertikale und horizontale Strecken auf einer diagonalen Geraden darstellen lassen, die sich genau dann schneiden, wenn zwischen ihnen eine Kante liegt. Anschließend betrachten wir die visuelle Komplexität von Graphen. Konkret untersuchen wir für bestimmte Graphklassen, wie viele Strecken für jede geradlinige Graphzeichnung notwendig sind, und, ob drei (oder mehr) verschiedene Streckensteigungen ausreichend sind, um alle Kanten zu zeichnen. Zuletzt beschäftigen wir uns mit der Frage, wie wir den Knoten eines Graphen mit gerichteten und ungerichteten Kanten (geordnete) Farben zuweisen können, sodass keine benachbarten Knoten dieselbe Farbe haben und Farben entlang gerichteter Kanten aufsteigend sind. Hierbei ist die spezielle Eigenschaft der betrachteten Graphen, dass sich die Knoten als Intervalle darstellen lassen, die sich genau dann überschneiden, wenn eine Kanten zwischen ihnen verläuft. Das letztgenannte Problem ist motiviert von einer Anwendung beim automatisierten Zeichnen von Kabelplänen mit vertikalen und horizontalen Streckenverläufen, womit wir uns im zweiten Teil befassen. Wir beschreiben einen Algorithmus, welcher die abstrakte Beschreibung eines Kabelplans entgegennimmt und daraus eine Zeichnung generiert, welche die speziellen Eigenschaften dieser Kabelpläne, wie Stecker und Gruppen von zusammengehörigen Drähten, berücksichtigt. Anschließend evaluieren wir die Qualität der so erzeugten Zeichnungen experimentell. Im dritten Teil befassen wir uns mit dem Abstrahieren bzw. Vereinfachen einer einzelnen Polylinie und eines Bündels von Polylinien. Bei diesem Problem sollen aus einer oder mehreren gegebenen Polylinie(n) so viele Knoten wie möglich entfernt werden, wobei jede resultierende Polylinie ihrem ursprünglichen Verlauf (nach einem gegeben Maß) hinreichend ähnlich bleiben muss.

Graph Drawing is a field of research that has application in any field of science that needs to visualize binary relations. This thesis covers various problems arising when drawing graphs, both in theoretical and applied settings. In the first and more theory-based part, we start by discussing how and to which degree graph drawings can be used to visually prove graph properties (such as connectivity) in an effective manner. Both for these visual proofs and for graph drawings in general, the visual complexity determines how well humans are able to perceive and process them. We find it thus paramount to minimize the visual complexity of drawings. For example, one measure for the visual complexity of a straight-line node-link diagram is the number of segments used. We prove lower bounds on the segment number of some planar graph classes. These bounds tell us how (visually) complex node-link diagrams (a traditional drawing style) of these graphs must be at least. Next, we consider obstacle representations, which can be far less (visually) complex in some cases, however, (usually) at the expense of being harder to understand. Next, we investigate the coloring of mixed and directional interval graphs. While this in itself is not a drawing problem, it has, among others, application in the Sugiyama framework, which is a widely used framework for layered orthogonal graph drawing. In the final chapter of the first part, we consider drawings of level graphs on few levels under a given set of precedence constraints. The two problems considered in the second part are motivated by applications in biology. First, we propose a drawing style for visualizing multispecies coalescent trees, which are composed of a species tree and associated gene trees, and then investigate various drawing algorithms. Second, we propose a model for visualizing geophylogenies, that is, species trees that label sites on maps, and then analyze various variants and algorithms to draw them. / Graphenzeichnen ist eine wissenschaftliche Disziplin, die in jeder anderen Wissenschaft Anwendung findet, in der binäre Relationen visualisiert werden. Diese Dissertation behandelt diverse Probleme, die beim Zeichnen von Graphen auftreten, sowohl in praktischen als auch in theoretischen Kontexten. Im ersten und eher theorieorientierten Teil diskutieren wir, wie und inwieweit Zeichnungen von Graphen benutzt werden können, um Eigenschaften von Graphen (wie zum Beispiel Zusammenhang) auf effektive Weise visuell zu beweisen. Sowohl für diese visuellen Beweise als auch für Zeichnungen von Graphen im Allgemeinen bestimmt die visuelle Komplexität, wie gut Menschen dazu in der Lage sind, Graphen wahrzunehmen und zu verarbeiten. Daher halten wir es für äußerst wichtig, die visuelle Komplexität von Zeichnungen zu minimieren. Ein Maß für die visuelle Kom- plexität von geradelinigen Node-Link-Diagrammen (einem traditionellen Zeichenstil) ist die Anzahl der benutzten Liniensegmente. Wir beweisen untere Schranken für die Segmentzahl einiger planarer Graphklassen, welche wiederum implizieren, wie (visuell) komplex Node-Link-Diagramme dieser Graphen mindestens sind. Als nächs- tes betrachten wir Hindernisrepräsentationen, die in manchen Fällen eine deutlich geringere (visuelle) Komplexität haben können, dafür allerdings (oft) schwerer zu verstehen sind. Danach untersuchen wir das Färben von gemischten sowie gerichteten Intervallgra- phen. Während es sich dabei nicht direkt um ein Zeichenproblem handelt, findet es unter anderem Anwendung im Sugiyama-Framework, einem weit verbreiteten Frame- work zum Erstellen von orthogonalen Lagenzeichnungen. Im letzten Kapitel des ersten Teils betrachten wir das Zeichnen von Levelgraphen unter Vorrangbeschränkungen. Die beiden Probleme, die wir im zweiten Teil betrachten, sind durch Anwendungen in der Biologie motiviert. Als erstes schlagen wir einen Zeichenstil für das Visualisieren von Multispecies-Coalescent-Bäumen vor, welche aus einem Artenbaum und damit verknüpften Genbäumen bestehen, und geben diverse Zeichenalgorithmen für solche Bäume an. Als zweites schlagen wir ein Modell zum Visualieren von Artenbäumen vor, die Orte auf Landkarten beschriften, und analysieren diverse Varianten und Algorithmen um diese zu zeichnen.

University, Diss., 2002--Saarbrücken.