2012/02/28 by Maia Fraser, Fraser, Maia
Computer Science · Mathematics · #05C10 #05C38 #05C40 #05C85 #57M99 #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Opportunistic and Delay-Tolerant Networks #Topological and Geometric Data Analysis #cs.CG #math.AT #msc:05C10 #msc:05C38 #msc:05C40 #msc:05C85 #msc:57M99
paper · pdf · doi:10.48550/arxiv.1202.6109
18 pages, 3 figures
arxiv created 2012/02/28 · openalex publication_date 2012/02/28 · arxiv updated 2012/02/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a local routing algorithm which guarantees delivery in all connected graphs embedded on a known surface of genus g. The algorithm transports O(glog n) memory and finishes in time O(g2n2), where n is the size of the graph. It requires access to a homology basis for the surface. This algorithm, GFR, may be viewed as a suitable generalization of Face Routing (FR), the well-known algorithm for plane graphs, which we previously showed does \it not guarantee delivery in graphs embedded on positive genus surfaces. The problem for such surfaces is the potential presence of homologically non-trivial closed walks which may be traversed by the right-hand rule. We use an interesting mathematical property of homology bases (proven in Lemma \reflem:connectFaceBdr) to show that such walks will not impede GFR. FR is at the base of most routing algorithms used in modern (2D) ad hoc networks: these algorithms all involve additional local techniques to deal with edge-crossings so FR may be applied. GFR should be viewed in the same light, as a base algorithm which could for example be tailored to sensor networks on surfaces in 3D. Currently there are no known efficient local, logarithmic memory algorithms for 3D ad hoc networks. From a theoretical point of view our work suggests that the efficiency advantages from which FR benefits are related to the codimension one nature of an embedded graph in a surface rather than the flatness of that surface (planarity).