# Routing in Geometric Graphs

## Prosenjit Bose, Carleton University

## October 17, 2017

A fundamental problem in computer science is that of finding a path in
a graph. When the whole graph is available, standard pathfinding
algorithms can be applied such as Depth-First Search or Dijkstra's
Algorithm. However, the problem of finding a path is more challenging
in an online setting when at every step of the computation, only local
information is available to the routing algorithm (such as the
neighbourhood of the current vertex in the path). The difficulty is in
deciding which edge to follow with only this local information.

We will explore different techniques for finding a path in a graph in
the online setting with an emphasis on finding paths
in geometric graphs (graphs whose vertices are points in the plane and
whose edges are segments between these points). We will highlight the
difficulties involved with routing in this setting and review some of
the currently best-known routing algorithms
in this setting.