Back to search

Carleton University

Improved Spanning and Routing Ratios on Geometric Graphs

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Carleton University
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hill, Darryl Richard

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright © 2019 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Carleton University
Base URL
carleton.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hill, Darryl Richard. Improved Spanning and Routing Ratios on Geometric Graphs. Doctoral thesis, Carleton University, 2019. https://hdl.handle.net/20.500.14718/39683