Theta-Graphs and Other Constrained Spanners

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.