Let G = ( V , E ) and G ' = ( V ' , E ' ) be two graphs. A k-inverse-adjacency-preserving mapping ? from G to G ' is a one-to-many and onto mapping from V to V ' satisfying the following: (1) Each vertex v ? V in G is mapped to a non-empty subset ? ( v ) ? V ' in G ' , the cardinality of ? ( v ) is at most k; (2) if u ? v , then ? ( u ) ? ? ( v ) = ? ; and (3) for any u ' ? ? ( u ) and v ' ? ? ( v ) , if ( u ' , v ' ) ? E ' , then ( u , v ) ? E . A vertex u ' in ? ( u ) is called a virtual location for u.Let ? be a k-inverse-adjacency-preserving-mapping (k-IAPM for short) from G to G ' . Let ? be a greedy drawing of G ' into a metric space M . Consider a message from u to be delivered to v in G. Using the k-IAPM ? from G to G ' , intuitively, one can treat the message to be routed as if it were from one virtual location u ' for u to one virtual location 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 ' can be computed from u ' to v ' while identifying all virtual locations for any vertex in G. Since ? inversely preserves adjacency from G ' to G, such a routing path 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 2 n - 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 2 n - 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 ? 5 n + 1 3 ? . Hence, there are at least ? n - 1 3 ? vertices that use only one virtual location.
['Huaming Zhang', 'Xiangzhi Kong']
On k-greedy routing algorithms