Local Routing on Tori
Maia Fraser
We show that face routing, the well-known geometric local routing algorithm for plane graphs introduced by Kranakis et al., does not in fact succeed for embedded graphs on the torus or higher genus surfaces. We then describe a generalization of face routing, and prove that this algorithm does provide a local routing algorithm for arbitrary graphs embedded in the torus. Finally we discuss extension of this type of algorithm to surfaces of genus g.
Keywords: Local routing, face routing, 3D sensor network, torus, surface.