Theta-Graphs and Other Constrained Spanners

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


van Renssen, Andre




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.


Computer Science




Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).