Computer Science – Computational Geometry
Scientific paper
2012-02-28
Computer Science
Computational Geometry
18 pages, 3 figures
Scientific paper
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(g\log n)$ memory and finishes in time $O(g^2n^2)$, 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 \ref{lem: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).
No associations
LandOfFree
Local Routing in Graphs Embedded on Surfaces of Arbitrary Genus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Local Routing in Graphs Embedded on Surfaces of Arbitrary Genus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local Routing in Graphs Embedded on Surfaces of Arbitrary Genus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-605483