Improved Spanning and Routing Ratios on Geometric Graphs

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.


Hill, Darryl Richard




In this thesis we examine a few classes of geometric graphs and improve the spanning and routing ratios on these graphs. We improve the routing ratio of the Delaunay triangulation from 5.90 to 3.56. We show that it is possible to route competitively on the Theta-4 graph with a routing ratio of 17. This bound on the routing ratio also serves to improve the bound on the spanning ratio from 237 to 17. We improve the spanning ratio of the convex hull of points arranged on the surface of a sphere from approximately 12.12 to 0.999 pi, and we improve the bound on the spanning ratio of the Theta-5 graph from 9.96 to 5.70.


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