Routing in Geometric Graphs

Abstract

This thesis investigates the spanning and routing properties of geometric graphs in the plane, focusing on establishing tight bounds and developing efficient local routing algorithms. First, we establish tight spanning and routing ratios for generalized Triangle-Distance Delaunay graphs, extending known results for equilateral triangle-based graphs. Second, we improve upper bounds on the spanning and routing ratios of polygon-Delaunay graphs with five to eight sides by generalizing an existing local routing algorithm. Third, we introduce a local routing algorithm for sparse directed planar graphs in the Yao-4-Infinity family, establishing the first constant routing ratio for these graphs and proving lower bounds on their spanning and routing ratios. Finally, we prove that the spanning ratio of the directed Theta-6 is exactly 5, closing the gap between previous upper and lower bounds through a novel approach based on linear programming.