On k-greedy routing algorithms

Let G=(V,E)G=(V,E) and G′=(V′,E′)G′=(V′,E′) be two graphs. A k-inverse-adjacency-preserving mapping ρ from G   to G′G′ is a one-to-many and onto mapping from V   to V′V′ satisfying the following: (1) Each vertex v∈Vv∈V in G   is mapped to a non-empty subset ρ(v)⊂V′ρ(v)⊂V′ in G′G′, the cardinality of ρ(v)ρ(v) is at most k  ; (2) if u≠vu≠v, then ρ(u)∩ρ(v)=∅ρ(u)∩ρ(v)=∅; and (3) for any u′∈ρ(u)u′∈ρ(u) and v′∈ρ(v)v′∈ρ(v), if (u′,v′)∈E′(u′,v′)∈E′, then (u,v)∈E(u,v)∈E. A vertex u′u′ in ρ(u)ρ(u) is called a virtual location for u.Let ρ be a k-inverse-adjacency-preserving-mapping (k-IAPM for short) from G   to G′G′. Let δ   be a greedy drawing of G′G′ into a metric space MM. Consider a message from u to be delivered to v in G. Using the k-IAPM ρ from G   to G′G′, intuitively, one can treat the message to be routed as if it were from one virtual location u′u′ for u   to one virtual location v′v′ for v, except that all the virtual locations of a vertex u   were identified with each other (which can be thought as instantaneously synchronized mirror sites for a particular website, for example). Then a routing path P′P′ can be computed from u′u′ to v′v′ while identifying all virtual locations for any vertex in G. Since ρ   inversely preserves adjacency from G′G′ to G  , such a routing path P′P′ corresponds to exactly one routing path P in G, which connects u to v.In this paper, we formalize the above intuition into a concept which we call k-greedy routing algorithm for a graph G with n vertices, where k refers to the maximum number of virtual locations any vertex of G can have. Using this concept, the result presented in [18] can be rephrased as a 3-greedy routing algorithm for 3-connected plane graphs, where the virtual coordinates used are from 1 to 2n−22n−2. In this paper, we present a 2-greedy routing algorithm for 3-connected plane graphs, where each vertex uses at least one but at most two virtual locations numbered from 1 to 2n−12n−1. For the special case of plane triangulations (in a plane triangulation, every face is a triangle, including the exterior face), the numbers used are further reduced to from 1 to ⌊5n+13⌋. Hence, there are at least ⌈n−13⌉ vertices that use only one virtual location.