Geometric Graphs: Reachability, Long Trees and Short Cycles

Abstract

Given a set S of n point sites, a geometric graph is a graph with S as its vertex set whose edges are drawn as line segments connecting the sites. The edges that are present between these sites can be defined by geometric properties of the site set. When talking about weighted edges, the weight of the edge connecting s and t is the Euclidean distance between s and t. One such class of graphs are spanning trees of the point set. That is, an acyclic graph defined on S such that all sites lie in the same connected component.

To define the second broad class of geometric graphs considered in this thesis, we extend each site with a radius. In this setting the sites can also be interpreted as disks, by using the site as the center. We consider two kinds of geometrically defined graphs on these extended sites. The first are disk graphs D(S). In a disk graph two sites are connected with an edge if and only if their corresponding disks intersect. The second type of graphs are transmission graphs T(S). These can be seen as a directed version of disk graphs. In a transmission graph a site s has a directed edge to a site t, if and only if t is contained in the disk defined by s.

We consider three main types of problems on these graphs:

TRIANGLES AND GIRTH IN DISK GRAPHS AND TRANSMISSION GRAPHS We give algorithms for finding a (shortest) triangle and more generally for finding short cycles. In general graphs, finding substantially faster algorithms than the naive approach is notoriously hard. However, better algorithms for special graph classes such as planar graphs exist in the literature. In this thesis, we obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that in a transmission graph a triangle can be detected and a shortest such triangle can be found in O(n log n) expected time. Furthermore, the weighted girth of a disk graph can be found within the same time bound. We also show that cycle with k edges in a transmission graph can be identified in O(n log n)+ n2^{O(k)} expected time. For the results on transmission graphs, we develop batched range query data structures that are of independent interest.

DYNAMIC DISK GRAPH CONNECTIVITY We consider the problem of designing data structures that maintain a disk graph under the deletion of sites, while allowing interleaved connectivity queries. First we consider the setting, where each site has a radius in the range [1,Ψ] for some fixed value Ψ. In this scenario, we give a data structure that supports m deletions in O( (n log^5 n + m log^9 n) λ_6(log n) + n logΨ log^4 n) overall expected time, with O((log n)/(log log n)) query time, where λ_6(n) is the length of a Davenport-Schinzel sequence of order 6. If we consider disk graphs without bounding the maximal allowed radius, we obtain a data structure that supports m deletions in O( (n log^6 n + m log^{10}n) λ_6(\log n) ) overall expected time, with the same O((log n)/(log log n)) time bound for queries.

LONG PLANE TREES We also consider spanning trees on the site set S. To be precise, we aim to find a plane spanning tree Topt of S that maximizes the total edge length |Topt|. Despite more than two decades of research, it remains open if this problem is NP-hard.

We take two approaches to the problem. The first is to follow the venue of approximation algorithms which was also the focus of previous research. We describe a polynomial-time algorithm to construct a plane tree Talg with diameter at most four and |Talg| >= 0.546 |Topt|, where |Topt| is the total edge length of an optimal plane spanning tree. This constitutes a significant improvement over the state of the art. Second, we consider exact polynomial time algorithms for trees of bounded diameter. We give an O(n^4) time algorithm for finding an exact solution for trees of diameter at most three and then extend this algorithm to special trees of diameter at most four.

Ein geometrischer Graph auf einer Menge von Punkten S⊆R^2 ist ein Graph mit S als Knotenmenge, dessen Kanten durch Strecken zwischen den Punkten dargestellt werden. Die Punkte können hierbei durch Angabe eines Radius auf Kreisscheiben erweitert werden. Die Kantenmenge wird dabei durch geometrische Eigenschaften von S definiert. In dieser Arbeit werden zwei Klassen von geometrischen Graphen betrachtet: Spannbäume und Graphen die auf Kreisscheiben definiert sind. Die zweite Klasse unterteilen wir in Disk Graphen und Transmissionsgraphen. Zwei Knoten in einem Disk Graphen sind mit einer Kante verbunden, wenn sich die zugehörigen Kreisschreiben schneiden. In einem Transmissionsgraphen sind zwei Knoten s und t verbunden, wenn t in der von s definierten Kreisscheibe liegt. Wir betrachten drei Arten von Problemen auf geometrischen Graphen:

DREIECKE UND TAILLENWEITE IN DISK GRAPHEN UND TRANSMISSIONSGRAPHEN Für Transmissionsgraphen beschreiben wir je einen Algorithmus, der ein Dreieck beziehungsweise ein kürzestes Dreieck in O(n\log n) erwarteter Zeit finden kann. Die Länge eines kürzesten gewichteten Kreises eines Disk Graphen, kann mit gleichem Zeitaufwand gefunden werden. Für Kreise mit maximal k Kanten in Transmissionsgraphen zeigen wir, dass diese in O(n log n)+n*2^{O(k)} erwarteter Zeit gefunden werden können. Für alle Ergebnisse in Transmissionsgraphen entwickeln wir Datenstrukturen für gesammelte Bereichsabfragen, die von unabhängigem Interesse sind.

DYNAMISCHE ZUSAMMENHANGSABFRAGEN IN DISK GRAPHEN Wir beschreiben verschiedene Datenstrukturen für Disk Graphen, die es erlauben einzelne Knoten zu löschen und Anfragen, ob zwei Knoten in der gleichen Zusammenhangskomponente liegen zu beantworten. Für die Situation in der alle Punkte einen Radius im Intervall [1,Ψ] haben, beschreiben wir eine Datenstruktur mit O((\log n)/(log log n)) amorisierter Anfragezeit, welche m Löschvorgänge in insgesamt O((n \log^5 n + m log^9 n) λ_6(\log n) + n logΨ log^4 n) erwarteter Zeit bearbeiten kann. Wenn der maximal erlaubte Radius nicht beschränkt ist, kann die Datenstrukur so erweitert werden, dass m Löschvorgänge in O((n log^6 n + m log^{10} n ) λ_6(\log n)) erwarteter Laufzeit durchgeführt werden können, ohne das sich die Anfragezeit verändert.

LANGE PLANARE SPANNBÄUME Wir betrachten zudem noch das Problem einen planaren Spannbaum mit maximaler Gesamtlänge zu finden. In diesem Zusammenhang beschreiben wir einen Approximationsalgorithmus, der einen Approximationsfaktor von 0.5467 erreicht. Zudem geben wir eine obere Schranke des Approximationsfaktors von 5/6 an, der von einem Baum mit Graphdurchmesser drei erreicht werden kann. Wir betrachten auch genaue Algorithmen für Sonderfälle. Mithilfe des Paradigmas der dynamischen Programmierung beschreiben wir einen Algorithmus, der in polynomieller Zeit den längsten Spannbaum mit Graphdurchmesser maximal drei findet. Dieser wird auf spezielle Bäume mit Graphdurchmesser maximal vier erweitert.