July 4, 2007 to July 6, 2007
Ulrik Brandes , University of Konstanz
Daniel Fleischer , University of Konstanz
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IV.2007.56
We consider routing methods for networks when geographic positions of nodes are available. Instead of using the original geographic coordinates, however, we precompute virtual coordinates using a barycentric layout. Combined with simple geometric routing rules, this greatly reduces the lengths of routes and outperforms algorithms working on the original coordinates. Along with experimental results we proof properties such as guaranteed message delivery and worst-case optimality. Our methods apply to static networks in which short routes are important, but memory for full routing tables is not available and the one-time-precomputation is affordable.
Ulrik Brandes, Daniel Fleischer, "Geographic Routing on Improved Coordinates", IV, 2007, 2013 17th International Conference on Information Visualisation, 2013 17th International Conference on Information Visualisation 2007, pp. 263-270, doi:10.1109/IV.2007.56