An optimal greedy routing algorithm for triangulated polygons (Q1947976)

In a greedy routing on a graph, each node forward messages to a neighbor that is closer to the destination. There are configurations of the graph where message delivery cannot always be guaranteed. A solution to this problems was to use a kind of virtual coordinates for the nodes instead of using real geometric coordinates. However, once the delivery guarantee problem was solved, another problem arose, that of achieving a simple representation of the virtual coordinates of each vertex. In the recent paper [\textit{H. Zhang} and \textit{S. Govindaiah}, Lect. Notes Comput. Sci. 6681, 58--69 (2011; Zbl 1329.90155)] the authors observed that in order for greedy routing to work, there is no need to embed the graph in a metric space. Instead, they used greedy embedding of graphs into semi-metric spaces. According with this approach, the main result in the paper under review is to show that any triangulated polygon with more than 3 vertices admits an optimal greedy routing algorithm, via a greedy embedding into an appropriate semi-metric space. The embedding is constructible in linear time and every node is representable in \(O(\text{deg}(\nu)\log(n))\) bits, being \(\text{deg}(\nu)\) the degree of the node \(\nu\).