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.

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

University, Diss., 2004--Heidelberg.

Techn. University, Diss., 2005--Berlin.

Techn. University, Diss., 2005--Darmstadt.

Der Vortrag erläutert, wie aus den Daten des OpenStreetMap-Projekts Karten erzeugt werden können. Neben dem Zusammensetzen einfacher Karten aus vorberechneten Tiles wird im Hauptteil erläutert, wie die Vektordaten zum Zeichnen benutzt werden können. Die Darstellung von Höhendaten schließt den Vortrag ab.

In dieser Arbeit werden Techniken beschrieben, die es erlauben (höhere) Ableitungen und Taylorapproximationen solcher Computerprogramme effizient zu berechnen. Auch inbesondere dann, wenn die Programme Algorithmen der numerischen linearen Algebra (NLA) enthalten. Im Gegensatz zur traditionellen algorithmischen Differentiation (AD), bei der die zugrunde liegenden Algorithmen um zusätzliche Befehlere erweitert werden, sind in dieser Arbeit die Zerlegungen durch definierende Gleichungen charakterisiert. Basierend auf den definierenden Gleichungen werden Strukturausnutzende Algorithmen hergeleitet. Genauer, neuartige Algorithmen für die Propagation von Taylorpolynomen durch die QR, Cholesky und reell-symmetrischen Eigenwertzerlegung werden präsentiert. Desweiteren werden Algorithmen für den Rückwärtsmodus der AD hergeleitet, welche im Wesentlichen nur die Faktoren der Zerlegungen benötigen. Im Vergleich zum traditionellen Ansatz, bei dem alle Zwischenergebnisse gespeichert werden, ist dies eine Reduktion von O(N^3) zu O(N^2) für Algorithmen mit O(N^3) Komplexität. N ist hier die Größe der Matrix. Zusätzlich kann bestehende, hoch-optimierte Software verwendet werden. Ein Laufzeitvergleich zeigt, dass dies im Vergleich zum traditionellen Ansatz zu einer Beschleunigung in der Größenordnung 100 führen kann. Da die NLA Funktionen als Black Box betrachtet werden, ist desweiteren auch der Berechnungsgraph um Größenordnungen kleiner. Dies bedeutet, dass Software, welche Operator Overloading benutzt, weniger Overhead hervorruft und auch weniger Speicher benötigt. / This thesis provides a framework for the evaluation of first and higher-order derivatives and Taylor series expansions through large computer programs that contain numerical linear algebra (NLA) functions. It is a generalization of traditional algorithmic differentiation (AD) techniques in that NLA functions are regarded as black boxes where the inputs and outputs are related by defining equations. Based on the defining equations, structure-exploiting algorithms are derived. More precisely, novel algorithms for the propagation of Taylor polynomials through the QR, Cholesky,- and real-symmetric eigenvalue decomposition are shown. Recurrences for the reverse mode of AD, which require essentially only the returned factors of the decomposition, are also derived. Compared to the traditional approach where all intermediates of an algorithm are stored, this is a reduction from O(N^3) to O(N^2) for algorithms with O( N^3) complexity. N denotes the matrix size. The derived algorithms make it possible to use existing high-performance implementations. A runtime comparison shows that the treatment of NLA functions as atomic can be more than one order of magnitude faster than an automatic differentiation of the underlying algorithm. Furthermore, the computational graph is orders of magnitudes smaller. This reduces the additional memory requirements, as well as the overhead, of operator overloading techniques to a fraction.

Oftmals kann ein Problem erst dadurch gelöst werden, indem seine Komplexität reduziert wird. Erst diese Reduktion ermöglicht die Verwendung von Lösungsansätzen, die für weniger komplexe Problemstellungen existieren. Für 3d-Objekte ist die Skelettierung der Mechanismus, der die Objekte auf eine niedrigere Dimension abbildet und dadurch deren Komplexität reduziert. Seit nunmehr 40 Jahren werden entsprechende Verfahren und darauf basierende Anwendungen entwickelt. In jüngster Zeit traten auf innovativen Forschungsgebieten innerhalb des Maschinenbaus, der Nanotechnologie, der Medizintechnik und nicht zuletzt der Computergrafik Probleme auf, die durch Skelettierung bewältigt wurden oder in naher Zukunft zu bewältigen sind. Mit der vorliegenden Dissertation wird an den aktuellen Stand der Forschung angeknüpft und ein Skelettierungsverfahren vorgestellt, das nicht auf den bisher üblichen kartesischen Gittern, sondern auf den sogenannten kubisch-raumzentrierten Gittern operiert. Dadurch ergeben sich eine Vielzahl positiver Eigenschaften, sowohl unter topologischen als auch rechentechnischen Aspekten. Die auf Gitterstrukturen basierenden Verfahren haben traditionell Schwierigkeiten, rotationsinvariante Skelette zu generieren. Diese Eigenschaft ist jedoch für eine Reihe von Applikationen wünschenswert. Eine Ausnahme bilden Verfahren, die zunächst ein Vektorfeld berechnen, das Abstoßungen vom Objektrand simuliert. Mithilfe dieser Strukturen können Skelettpunkte identifiziert werden, die von der Gitterstruktur unabhängig sind. Allerdings sind die Verfahren, die derartige Skelette erzeugen, extrem ineffizient: Bezogen auf die Anzahl der Objektgitterpunkte ist die Komplexität quadratisch. Deshalb ist ein weiterer Schwerpunkt dieser Arbeit, eine qualitativ hochwertige Approximation des Vektorfeldes in linearer Zeitkomplexität zu erzeugen. Die zusätzlichen Informationen, die aus diesen Vektorfeldern gewonnen werden, kommen innerhalb des ursprünglichen Skelettierungsverfahrens zum Einsatz, um die Vorteile beider Verfahren zu kombinieren. Die auf diese Weise erzeugten eindimensionalen Skelettstrukturen der 3d-Objekte eignen sich für eine Vielzahl von Anwendungen. Drei Anwendungen, namentlich die Klassifizierung, die Segmentierung und die Manipulierung werden gezeigt. Für die Klassifizierung werden die erzeugten Skelette in eine Graphrepräsentation transformiert. Hierfür werden zwei Verfahren vorgestellt und darüber hinaus erläutert, wie die Graphrepräsentation optimiert und mit Attributen versehen werden kann. Insbesondere die Attributierung (z. B. mit Distanz- oder Krümmungsinformationen) ist von großer Bedeutung, da der Graph zunächst die Objektform nur grob abstrahiert und dadurch kein detaillierter Vergleich zwischen Objekten möglich wäre. Für die Segmentierung und die Deformierung von 3d-Objekten besteht der wichtigste Beitrag dieser Dissertation darin, eine präzise Zuordnung zwischen Abschnitten des Graphen und Meshregionen durchzuführen, die erforderlich ist, um Änderungen an der Graphstruktur (Auftrennen oder Deformieren) direkt auf das Mesh übertragen zu können. Hierfür wird eine spezielle Datenstruktur präsentiert, die diese Zuordnung ermöglicht, ohne die Komplexität des Skelettierungsverfahrens zu verschlechtern. Ein breites Spektrum an Vorschlägen für zukünftige, auf dieser Dissertation aufbauende Forschungsthemen schließen die Arbeit ab.

Verschiedene simultan wirkende Signale beeinflussen die Signalverarbeitung und die Genregulation von Säugetieren auf der systemischen Ebene. Die Signale müssen integriert und in ihrem jeweiligen Zusammenhang bewertet werden. Dabei können die Signale auch synergistisch miteinander interagieren, wobei dann einzig durch dieses Zusammenspiel auf genregulatorischer Ebene neue Funktionen induziert werden. Gängige experimentelle Ansätze zur Detektion von synergistischen Interaktionen erkennen zwar die beeinflussten Gene, aber die zugrunde liegenden Mechanismen bleiben unklar. In dieser Arbeit wurde deshalb ein globales systembiologisches Verfahren entwickelt, welches Synergien anhand ihrer generellen topologischen Eigenschaften in einem bipartiten Graphen detektiert. Das für die Analyse notwendige globale bipartite und mechanistische Signaltransduktionsreferenznetzwerk wurde auf der Basis experimentell verifizierter Daten aus verschiedenen Datenbanken sowie aktueller Literatur in dieser Arbeit rekonstruiert. Synergien sind besonders im Immunsystem relevant, wo verschiedene Signale parallel eine Immunreaktion auslösen. Eine adäquate Antwort kann dabei nur durch eine gleichzeitige und präzise regulierte Bewertung der wirkenden Signale ermöglicht werden. Das entwickelte Verfahren wurde auf die, für die Immunantwort essentiellen, Immunsignale Interleukin-3 (IL-3) und humanes Influenza Virus (Flu) in menschlichen plasmacytoiden dendritischen Zellen, einem Immunzelltyp, angewandt. Um synergistische Effekte während der Signalintegration zu untersuchen wurde das Referenznetzwerk auf die säugerspezifischen, in pDC präsenten und durch IL-3 und Flu aktivierten Signalpfade eingeschränkt. Es wurden unter anderem die synergistischen Interaktionspunkte detektiert, ihre regulierten Transkriptionsfaktoren sowie die durch sie regulierten Zielgene. Durch den Vergleich der ausgelösten Funktionen und der jeweils induzierten Signalwege konnte gezeigt werden, dass das entwickelte Verfahren die immunrelevanten synergistisch regulierten Gene besser detektiert als ein vergleichbares experimentelles Verfahren.

Oftmals kann ein Problem erst dadurch gelöst werden, indem seine Komplexität reduziert wird. Erst diese Reduktion ermöglicht die Verwendung von Lösungsansätzen, die für weniger komplexe Problemstellungen existieren. Für 3d-Objekte ist die Skelettierung der Mechanismus, der die Objekte auf eine niedrigere Dimension abbildet und dadurch deren Komplexität reduziert. Seit nunmehr 40 Jahren werden entsprechende Verfahren und darauf basierende Anwendungen entwickelt. In jüngster Zeit traten auf innovativen Forschungsgebieten innerhalb des Maschinenbaus, der Nanotechnologie, der Medizintechnik und nicht zuletzt der Computergrafik Probleme auf, die durch Skelettierung bewältigt wurden oder in naher Zukunft zu bewältigen sind. Mit der vorliegenden Dissertation wird an den aktuellen Stand der Forschung angeknüpft und ein Skelettierungsverfahren vorgestellt, das nicht auf den bisher üblichen kartesischen Gittern, sondern auf den sogenannten kubisch-raumzentrierten Gittern operiert. Dadurch ergeben sich eine Vielzahl positiver Eigenschaften, sowohl unter topologischen als auch rechentechnischen Aspekten. Die auf Gitterstrukturen basierenden Verfahren haben traditionell Schwierigkeiten, rotationsinvariante Skelette zu generieren. Diese Eigenschaft ist jedoch für eine Reihe von Applikationen wünschenswert. Eine Ausnahme bilden Verfahren, die zunächst ein Vektorfeld berechnen, das Abstoßungen vom Objektrand simuliert. Mithilfe dieser Strukturen können Skelettpunkte identifiziert werden, die von der Gitterstruktur unabhängig sind. Allerdings sind die Verfahren, die derartige Skelette erzeugen, extrem ineffizient: Bezogen auf die Anzahl der Objektgitterpunkte ist die Komplexität quadratisch. Deshalb ist ein weiterer Schwerpunkt dieser Arbeit, eine qualitativ hochwertige Approximation des Vektorfeldes in linearer Zeitkomplexität zu erzeugen. Die zusätzlichen Informationen, die aus diesen Vektorfeldern gewonnen werden, kommen innerhalb des ursprünglichen Skelettierungsverfahrens zum Einsatz, um die Vorteile beider Verfahren zu kombinieren. Die auf diese Weise erzeugten eindimensionalen Skelettstrukturen der 3d-Objekte eignen sich für eine Vielzahl von Anwendungen. Drei Anwendungen, namentlich die Klassifizierung, die Segmentierung und die Manipulierung werden gezeigt. Für die Klassifizierung werden die erzeugten Skelette in eine Graphrepräsentation transformiert. Hierfür werden zwei Verfahren vorgestellt und darüber hinaus erläutert, wie die Graphrepräsentation optimiert und mit Attributen versehen werden kann. Insbesondere die Attributierung (z. B. mit Distanz- oder Krümmungsinformationen) ist von großer Bedeutung, da der Graph zunächst die Objektform nur grob abstrahiert und dadurch kein detaillierter Vergleich zwischen Objekten möglich wäre. Für die Segmentierung und die Deformierung von 3d-Objekten besteht der wichtigste Beitrag dieser Dissertation darin, eine präzise Zuordnung zwischen Abschnitten des Graphen und Meshregionen durchzuführen, die erforderlich ist, um Änderungen an der Graphstruktur (Auftrennen oder Deformieren) direkt auf das Mesh übertragen zu können. Hierfür wird eine spezielle Datenstruktur präsentiert, die diese Zuordnung ermöglicht, ohne die Komplexität des Skelettierungsverfahrens zu verschlechtern. Ein breites Spektrum an Vorschlägen für zukünftige, auf dieser Dissertation aufbauende Forschungsthemen schließen die Arbeit ab.