Abstract
In this paper, we generalize the greedy routing concept to use semi-metric spaces. We prove that any connected n-vertex graph G admits a greedy embedding onto an appropriate semi-metric space such that (1) each vertex v of the graph is represented by up to k virtual coordinates (where the numbers are from 1 to 2n − 1 and k ≤ deg(v)); and (2) using an appropriate distance definition, there is always a distance decreasing path between any two vertices in G. In particular, we prove that, for a 3-connected plane graph G, there is a greedy embedding of G such that: (1) the greedy embedding can be obtained in linear time; and (2) each vertex can be represented by at most 3 virtual coordinates from 1 to 2n − 1. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in O(log n) bits.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angelini, P., Di Battista, G., Frati, F.: Succinct greedy drawings do not always exist. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 171–182. Springer, Heidelberg (2010)
Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 26–37. Springer, Heidelberg (2009)
Barnette, D.: 3-trees in polyhedral graphs. Isreal Journal of Mathematics 18, 731–736 (1966)
Bondy, J.A., Murty, U.S.R.: Graph theory with applications. Elsevier Science Publishing Co., Inc., Amsterdam
Comer, D.: Internetworking with TCP/IP, Volume 1: Principles, Protocols, and Architecture. Prentice-Hall, Inc., Upper Saddle River (2006)
Ben-Chen, M., Gotsman, C., Wormser, C.: Distributed computation of virtual coordinates. In: Proc. SoCG 2007, pp. 210–219 (2007)
Czumaj, A., Strothmann, W.-B.: Bounded degree spanning trees (Extended abstract). In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol. 1284, pp. 104–117. Springer, Heidelberg (1997)
Dhandapani, R.: Greedy drawings of triangulations. In: Proc. SODA 2008, pp. 102–111 (2008)
Eppstein, D., Goodrich, M.T.: Succinct greedy graph drawing in the hyperbolic plane. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 14–25. Springer, Heidelberg (2009)
Goodrich, M.T., Strash, D.: Succinct Greedy Geometric Routing in the Euclidean Plane, submitted ot arXiv: 0812.3893v3 (October 2009)
Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. In: Proc. FOCS 2008, pp. 337–346 (2008)
Lillis, K.M., Pemmaraju, S.V.: On the efficiency of a local iterative algorithm to compute delaunay realizations. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 69–86. Springer, Heidelberg (2008)
Muhammad, R.B.: A distributed geometric routing algorithm for ad hoc wireless networks. In: Proceedings of the 4th International Conference on Information Technology (ITNG 2007), pp. 961–963. IEEE Press, Los Alamitos (2007)
Kleinberg, R.: Geographic routing using hyperbolic space. In: INFOCOM 2007: 26th IEEE International Conference on Computer Communications, pp. 1902–1909 (2007)
Rao, A., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location information. In: Proc. Mobicom 2003, pp. 96–108 (2003)
Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theoretical Computer Science 344(1), 3–14 (2005)
Strothmann, W.B.: Bounded degree spanning trees, Ph.D. thesis, Heinz-Nixdorf-Institut, Universität, Paderborn (1997)
Tanenbaum, A.S.: Computer networks, 4th edn. Prentice-Hall, Inc., Upper Saddle River (2003)
He, X., Zhang, H.: Schnyder greedy routing algorithm. In: Kratochvíl, J., Li, A., Fiala, J., Kolman, P. (eds.) TAMC 2010. LNCS, vol. 6108, pp. 271–283. Springer, Heidelberg (2010)
He, X., Zhang, H.: On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs. In: The Proceedings of SODA, the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1477–1486 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, H., Govindaiah, S. (2011). Greedy Routing via Embedding Graphs onto Semi-metric Spaces. In: Atallah, M., Li, XY., Zhu, B. (eds) Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol 6681. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21204-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-21204-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21203-1
Online ISBN: 978-3-642-21204-8
eBook Packages: Computer ScienceComputer Science (R0)