Geometric routing

This thesis is concerned with the problem of optimal routing in geometric graphs. A geometric graph is a graph in which each node has location information, and edges have some geometrical constraints. The problems considered in this thesis fall into two main categories: (i) routing in ad hoc wireless networks, (ii) routing through weighted regions.; The fundamental problem in ad hoc wireless networks is broadcasting messages without flooding and it is modeled on unit disk graphs.; The Weighted Region Problem deals with finding an optimal route between two points in the plane, and is modeled on a planar graph where paths are allowed to pass through the faces.; The main results of this thesis are: (a) an improved approximation result for a unit disk covering problem, (b) an elimination scheme for a minimum forwarding set problem, (c) analysis of two-hop realizable graphs, (d) exact solutions for simple weighted region problems, (e) algorithms to reduce distortions in raster paths, (f) comparison and analysis of vector based algorithms.