Succinct Greedy Graph Drawing in the Hyperbolic Plane

Eppstein, David and Goodrich, Michael T. (2009) Succinct Greedy Graph Drawing in the Hyperbolic Plane. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 14-25 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_3).

Full text not available from this repository.

Abstract

We describe a method for producing a greedy embedding of any n- vertex simple graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M ’s destination. Our algorithm produces succinct drawings, where vertex positions are represented using O(log n) bits and distance comparisons may be performed efficiently using these representations.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_3
Classifications:P Styles > P.420 Hyper
ID Code:893

Repository Staff Only: item control page

References

Alstrup, S., Lauridsen, P.W., Sommerlund, P., Thorup, M.: Finding cores of limited length. In: WADS ’97. LNCS, vol. 1272, pp. 45–54. Springer-Verlag (1997)

Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with Guaranteed Delivery in Ad Hoc Wireless Networks. Wireless Networks 6(7), 609–616 (2001)

Chen, M.B., Gotsman, C., Wormser, C.: Distributed computation of virtual coordinates. In: Proc. 23rd Symp. Computational Geometry (SoCG ’97). pp. 210–219 (2007)

Dhandapani, R.: Greedy drawings of triangulations. In: Proc. 19th ACM-SIAM Symp. Discrete Algorithms (SODA ’08). pp. 102–111 (2008)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Gilbert, E.N., Moore, E.F.: Variable-Length binary

encodings. Bell System Tech. J. 38, 933–968 (1959)

Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proc. 6th ACM Mobile Computing and Networking (MobiCom). pp. 243–254 (2000)

Kleinberg, R.: Geographic Routing Using Hyperbolic Space. In: Proc. 26th IEEE Int. Conf. Computer Communications (INFOCOM 2007). pp. 1902–1909. IEEE Press (2007)

Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. 11th Canad. Conf. Computational Geometry (CCCG). pp. 51–54 (1999)

Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: Proc. 22nd ACM Symp. Principles of Distributed Computing (PODC). pp. 63–72 (2003)

Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proc. 6th ACM Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM). pp. 24–33 (2002)

Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-Case optimal and average-case efficient geometric ad-hoc routing. In: Proc. 4th ACM Symp. Mobile Ad Hoc Networking & Computing (MobiHoc). pp. 267–278 (2003)

Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. In: Proc. 49th IEEE Symp. Foundations of Computer Science (FOCS) (2008)

Lillis, K.M., Pemmaraju, S.V.: On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations. In: Workshop on Experimental Algorithms (WEA) (2008)

Maymounkov, P.: Greedy Embeddings, Trees, and Euclidean vs. Lobachevsky Geometry.Online manuscript, M.I.T. (2006), http://pdos.csail.mit.edu/petar/papers/maymounkov-greedy-prelim.pdf

Muhammad, R.B.: A distributed geometric routing algorithm for ad hoc wireless networks. In: Proc. IEEE Conf. Information Technology (ITNG). pp. 961–963 (2007)

Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theor. Comput. Sci. 344(1), 3–14 (2005)

Rao, A., Ratnasamy, S., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location information. In: Proc. 9th Int. Conf. Mobile Computing and Networking (MobiCom ’03). pp. 96–108. ACM, New York, NY, USA (2003)

Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253–1262 (1988)

Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms. pp. 138–148 (1990)

Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comp. and Sys. Sci. 26(3), 362–391 (1983)