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.