In dieser Arbeit wird die Übertragung des Konzepts des Tree Covers auf die Kürzeste-Wege-Metrik von Unit Disk Graphen untersucht.

Ein α-Tree Cover ist eine Überdeckung eines Graphen durch eine Menge von Bäumen. Für jedes Knotenpaar muss dabei ein Baum aus dem Tree Cover existieren, in dem die Kürzeste-Wege-Distanz um höchstens den Faktor α verzerrt wird. Viele Distanzprobleme lassen sich auf dieser Menge von Bäumen anstelle des ursprünglichen Graphen effizient approximieren.

Für die euklidische Metrik, Metriken mit konstanter Doubling Dimension und planare Graphen existieren bereits effiziente Algorithmen zur Konstruktion kompakter Tree Cover. Es wird untersucht, inwieweit sich diese Ansätze auf die Kürzeste-Wege-Metrik von Unit Disk Graphen übertragen lassen. Anschließend wird ein eigener Algorithmus zur Konstruktion eines Tree Covers auf Unit Disk Graphen vorgestellt, der auf einer Well-Separated Pair Decomposition basiert. Das resultierende Tree Cover wird analysiert und mit den bestehenden Verfahren anderer metrischer Räume verglichen.

Für dichte oder gleichmäßig verteilte Unit Disk Graphen wird dabei im schlechtesten Fall ein (1 + ε)-Tree Cover mit konstantem Verzerrungsfaktor in subquadratischer Zeit konstruiert, wobei subquadratisch viele Kanten gespeichert werden müssen. Zudem lässt sich für jedes Punktepaar in konstanter Zeit ein passender Baum finden, der die Distanz minimal verzerrt, sodass das Tree Cover für effizientes Routing in zum Beispiel Ad-hoc-Netzwerken angewendet werden kann.