Succinct Greedy Drawings Do Not Always Exist

Di Battista, Giuseppe and Frati, Fabrizio and Angelini, Patrizio (2010) Succinct Greedy Drawings Do Not Always Exist. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 171-182 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_17).

Full text not available from this repository.

Abstract

A greedy drawing is a graph drawing containing a distance-decreasing path for every pair of nodes. A path (v0 , v1 , . . . , vm ) is distance-decreasing if d(vi , vm ) < d(vi−1 , vm ), for i = 1, . . . , m. Greedy drawings easily support geographic greedy routing. Hence, a natural and practical problem is the one of constructing greedy drawings in the plane using few bits for representing vertex Cartesian coordinates and using the Euclidean distance as a metric. We show that there exist greedy-drawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_17
Classifications:Z Theory > Z.250 Geometry
ID Code:1064

Repository Staff Only: item control page

References

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)

Dhandapani, R.: Greedy drawings of triangulations. In: Huang, S.T. (ed.) SODA 2008, pp. 102–111 (2008)

Di Battista, G., Lenhart, W., Liotta, G.: Proximity drawability: a survey. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 328–339. Springer, Heidelberg (1995)

Di Battista, G., Tamassia, R., Tollis, I.G.: Area requirement and symmetry display of planar upward drawings. Discrete & Computational Geometry 7, 381–401 (1992)

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)

Kaufmann, M.: Polynomial area bounds for MST embeddings of trees. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 88–100. Springer, Heidelberg (2008)

Kleinberg, R.: Geographic routing using hyperbolic space. In: INFOCOM 2007, pp. 1902– 1909 (2007)

Knaster, B., Kuratowski, C., Mazurkiewicz, C.: Ein beweis des fixpunktsatzes fur n dimensionale simplexe. Fundamenta Mathematicae 14, 132–137 (1929)

Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. In: FOCS 2008, pp. 337–346 (2008) 10. Monma, C.L., Suri, S.: Transitions in geometric minimum spanning trees. Discrete & Computational Geometry 8, 265–293 (1992)

Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theoretical Computer Science 344(1), 3–14 (2005)

Penna, P., Vocca, P.: Proximity drawings in polynomial area and volume. Computational Geometry 29(2), 91–116 (2004)

Rao, A., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location information. In: Johnson, D.B., Joseph, A.D., Vaidya, N.H. (eds.) MOBICOM 2003, pp. 96– 108 (2003)

Schnyder, W.: Embedding planar graphs on the grid. In: SODA 1990, pp. 138–148 (1990)