Succinct greedy graph drawing in the hyperbolic plane. (English) Zbl 1213.68444
Tollis, Ioannis G. (ed.) et al., Graph drawing. 16th international symposium, GD 2008, Heraklion, Crete, Greece, September 21–24, 2008. Revised papers. Berlin: Springer (ISBN 978-3-642-00218-2/pbk). Lecture Notes in Computer Science 5417, 14-25 (2009).
Summary: 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.
For the entire collection see [Zbl 1156.68007].
For the entire collection see [Zbl 1156.68007].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Alstrup, S.; Lauridsen, P. W.; Sommerlund, P.; Thorup, M.; Rau-Chaplin, A.; Dehne, F.; Sack, J.-R.; Tamassia, R., Finding cores of limited length, Algorithms and Data Structures, 45-54 (1997), Heidelberg: Springer, Heidelberg · Zbl 1517.68270 · doi:10.1007/3-540-63307-3_47 |
| [2] | Bose, P.; Morin, P.; Stojmenović, I.; Urrutia, J., Routing with Guaranteed Delivery in Ad Hoc Wireless Networks, Wireless Networks, 6, 7, 609-616 (2001) · Zbl 0996.68012 · doi:10.1023/A:1012319418150 |
| [3] | Chen, M.B., Gotsman, C., Wormser, C.: Distributed computation of virtual coordinates. In: Proc. 23rd Symp. Computational Geometry (SoCG 1997), pp. 210-219 (1997) · Zbl 1221.68292 |
| [4] | Dhandapani, R.: Greedy drawings of triangulations. In: Proc. 19th ACM-SIAM Symp. Discrete Algorithms (SODA 2008), pp. 102-111 (2008) · Zbl 1192.68741 |
| [5] | de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 1, 41-51 (1990) · Zbl 0728.05016 · doi:10.1007/BF02122694 |
| [6] | Gilbert, E. N.; Moore, E. F., Variable-Length binary encodings, Bell System Tech. J., 38, 933-968 (1959) · doi:10.1002/j.1538-7305.1959.tb01583.x |
| [7] | 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) |
| [8] | Kleinberg, R., Geographic Routing Using Hyperbolic Space, Proc. 26th IEEE Int. Conf. Computer Communications (INFOCOM 2007), 1902-1909 (2007), Los Alamitos: IEEE Press, Los Alamitos · doi:10.1109/INFCOM.2007.221 |
| [9] | Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. 11th Canad. Conf. Computational Geometry (CCCG), pp. 51-54 (1999) |
| [10] | 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) · Zbl 1321.68052 |
| [11] | 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) |
| [12] | 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) |
| [13] | Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. In: Proc. 49th IEEE Symp. Foundations of Computer Science (FOCS) (2008) · Zbl 1230.05269 |
| [14] | Lillis, K. M.; Pemmaraju, S. V.; McGeoch, C. C., On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations, Experimental Algorithms, 69-86 (2008), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-68552-4_6 |
| [15] | Maymounkov, P.: Greedy Embeddings, Trees, and Euclidean vs. Lobachevsky Geometry. M.I.T (manuscript, 2006), http://pdos.csail.mit.edu/ petar/papers/maymounkov-greedy-prelim.pdf |
| [16] | Muhammad, R.B.: A distributed geometric routing algorithm for ad hoc wireless networks. In: Proc. IEEE Conf. Information Technology (ITNG), pp. 961-963 (2007) |
| [17] | Papadimitriou, C. H.; Ratajczak, D., On a conjecture related to geometric routing, Theor. Comput. Sci., 344, 1, 3-14 (2005) · Zbl 1079.68078 · doi:10.1016/j.tcs.2005.06.022 |
| [18] | Rao, A.; Ratnasamy, S.; Papadimitriou, C. H.; Shenker, S.; Stoica, I., Geographic routing without location information, Proc. 9th Int. Conf. Mobile Computing and Networking (MobiCom 2003), 96-108 (2003), New York: ACM, New York · doi:10.1145/938985.938996 |
| [19] | Schieber, B.; Vishkin, U., On finding lowest common ancestors: simplification and parallelization, SIAM J. Comput., 17, 6, 1253-1262 (1988) · Zbl 0669.68049 · doi:10.1137/0217079 |
| [20] | Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pp. 138-148 (1990) · Zbl 0786.05029 |
| [21] | Sleator, D. D.; Tarjan, R. E., A data structure for dynamic trees, J. Comp. and Sys. Sci., 26, 3, 362-391 (1983) · Zbl 0509.68058 · doi:10.1016/0022-0000(83)90006-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
