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.