## Creator:

## Date:

## Abstract:

We provide improved upper bounds on the spanning ratio of various geometric graphs,

one of which being θ-graphs. Given a set of points in the plane, a θ-graph partitions

the plane around each vertex into m disjoint cones, each having aperture θ = 2π/m,

and adds an edge to the `closest' vertex in each cone. We provide tight bounds on a

large number of these graphs, for different values of m, and improve the upper bounds

on the other θ-graphs.

We also study the ordered setting, where the θ-graph is build by inserting

vertices

one at a time and we consider only previously-inserted vertices when determining the

`closest' vertex in each cone. We improve some of the upper bounds in this setting, but

our main contribution is that we show that a number of θ-graphs that are spanners

in the unordered setting are not spanners in the ordered setting.

Our main topic, however, is the constrained setting: We introduce line segment

constraints that the edges of the graph are not allowed to cross and show that the

upper bounds shown for θ-graphs carry over to constrained

θ-graphs. We also construct

a bounded-degree plane spanner based on the constrained half-θ6-graph (the

constrained Delaunay graph whose empty convex shape is an equilateral triangle) and

we provide a local competitive routing algorithm for the constrained θ6-graph.

Next, we look at constrained Yao-graphs, which are comparable to constrained θ-

graphs, but use a different distance function, and show that these graphs are spanners.

Finally, we look at constrained generalized Delaunay graphs: Delaunay graphs

where the empty convex shape is not

necessarily a circle, but can be any convex

shape. We show that regardless of the convex shape, these graphs are connected,

plane spanners. We then proceed to improve the spanning ratio for a subclass of

these graphs, where the empty convex shape is an arbitrary rectangle.