Instances of geometric problems usually have both a concrete geometric and a more abstract representation. Given the geometric representation it is often easy to find the abstract one while the converse is not true: Given an abstract representation it can be challenging to find a geometric one or decide that no such representation exists. How challenging it is generally depends on the complexity of the given abstract representation. In this thesis we study two different problems with the aforementioned properties:
Weak Unit Disk Contact Representations. A unit disk contact representation (UDCR) of a graph is a set of interior-disjoint unit disks in the plane (each disk corresponds to one node) such that two disks touch if and only if their corresponding nodes have an edge. The notion of weak unit disk contact representations (weak UDCRs) weakens this condition and only enforces that two disks must touch if the corresponding nodes have an edge. If two nodes don’t have an edge, their corresponding disks are still allowed to touch. The problem comes in two flavors: the first are graphs without embedding where the neighboring disks can be arranged in any order. Here we show that the problem is NP-hard for trees and provide a linear time algorithm for caterpillars, which are trees that become paths when all leaves are removed once. The second flavor are graphs with a fixed embedding where a given order of the neighboring disks in a weak UDCR must be respected. Here we show that the problem is already NP-hard for general caterpillars. We also show that we can decide in linear time whether a caterpillar has a weak UDCR that can be placed on a triangular grid and whose disks for the path of inner nodes are strictly x-monotone.
Colored Nearest Neighbor Graphs. In the second part of this thesis we look at a one-dimensional geometric problem. Here we are given a set of one-dimensional points and a list of line segments between neighboring points such that every point has at least one incident line segment. We then assign a non-empty set of colors to each point and for each assigned color create an edge in this color between the point and the closest point that also has this color. A valid assignment of colors to the points has two properties: First, every created edge corresponds to a line segment between the same endpoints and for every line segment there exists such an edge. Second, there can be no two edges with different colors between two points. It is easy to see that such a valid color assignment always exists: select a unique color for each line segment and assign this color to both endpoints. In this thesis we answer the question of how many colors are needed for a given input and how long it takes to find a valid assignment. We show that for both one and two colors we can decide whether a valid assignment exists (and also find it) in linear time. To this end we make some structural observations that help us narrow down the possible color assignments that we need to look at. There are two defining structures responsible for increasing the necessary number of colors: local maxima which are line segments that are longer than both adjacent line segments, and small gaps which are missing line segments between two points such that the missing line segment is not longer than both adjacent line segments. We show that in the worst case the number of local maxima increases the number of colors logarithmically and the number of small gaps increases them linearly. Finally, we provide a dynamic program that, given an input and a number of colors, finds a valid color assignment with this number of colors or returns that no valid color assignment exists. The running time of this algorithm is exponential in the number of colors.
Schwache Kontaktdarstellungen von Einheitskreisscheiben. Eine schwache Kontaktdarstellung von Einheitskreisscheiben (sKvE) eines Graphen ist eine Menge von sich im Inneren nicht schneidenden Einheitskreisscheiben in der Ebene bei der jede Kreisscheibe einem Knoten des Graphen zugeordnet ist. Dabei müssen sich je zwei Kreisscheiben berühren, also im Rand schneiden, wenn die zugehörigen Knoten mit einer Kante verbunden sind. Die Kreisscheiben von nicht per Kante verbundenen Knoten dürfen sich trotzdem berühren. Wir betrachten zwei Varianten des Problems: Bei Graphen ohne Einbettung ist die Platzierung der benachbarten Kreisscheiben egal. Das Problem ist NP-schwer für Bäume und in linearer Zeit lösbar für Raupengraphen (Bäume, die zu Pfaden werden, wenn alle Blätter entfernt werden). Bei Graphen mit einer festen Einbettung ist die Reihenfolge der Platzierung der benachbarten Kreisscheiben vorgegeben. Hier zeigen wir, dass das Problem bereits NP-schwer für allgemeine Raupengraphen ist. Beschränken wir uns auf sKvE, die auf einem regelmäßigen Dreiecksgitter platziert werden können und bei denen die Kreisscheiben der inneren Knoten streng x-monoton sind, so ist das Problem hier ebenfalls in linearer Zeit lösbar
Gefärbte Nächste-Nachbarn-Graphen. Hier ist eine Menge eindimensionaler Punkte und eine Liste von Strecken zwischen benachbarten Punkten gegeben, sodass jeder Punkt mindestens eine anliegende Strecke hat. Jedem Punkt soll eine nichtleere Menge von Farben zugewiesen werden. Für jede Farbe erzeugen wir eine Kante zwischen diesem Punkt und dem nächstgelegenen mit derselben Farbe. Eine gültige Farbzuordnung erzeugt für jede Strecke genau eine Kante zwischen denselben Endpunkten; zwei Kanten mit verschiedenen Farben zwischen den gleichen Punkten sind verboten. Wählen wir für die Endpunkte jeder Strecke eine eigene Farbe, so ist dies immer eine gültige Lösung. Daher ist die Frage, wie wenig Farben im besten Fall benötigt werden. Für ein und zwei Farben können wir in linearer Zeit eine gültige Farbzuordnung finden, falls sie existiert. Zwei Unterstrukturen sind entscheidend für die Anzahl der benötigten Farben: Lokale Maxima, also Strecken die länger sind als beide benachbarten Strecken, und schmale Lücken, also fehlende Strecken, bei denen mindestens eine benachbarte Strecke länger ist. Die Anzahl der Farben wächst im schlimmsten Fall logarithmisch in der Anzahl der lokalen Maxima und linear in der Anzahl der kleinen Lücken. Wir beschreiben schließlich ein dynamisches Programm, das bei einer Eingabe und einer Anzahl von Farben eine gültige Farbzuordnung mit dieser Anzahl von Farben findet oder zurückgibt, dass keine gültige Farbzuordnung existiert. Die Laufzeit dieses Algorithmus ist exponentiell in der Anzahl der Farben.
