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
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.