Abstract
A greedy drawing is a graph drawing containing a distance-decreasing path for every pair of nodes. A path (v 0,v 1,...,v m ) is distance-decreasing if d(v i ,v m ) < d(v i − 1,v m ), 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.
This work is partially supported by the Italian Ministry of Research, Grant number RBIP06BZW8, FIRB project “Advanced tracking system in intermodal freight transportation”.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angelini, P., Di Battista, G., Frati, F. (2010). Succinct Greedy Drawings Do Not Always Exist. In: Eppstein, D., Gansner, E.R. (eds) Graph Drawing. GD 2009. Lecture Notes in Computer Science, vol 5849. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11805-0_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-11805-0_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11804-3
Online ISBN: 978-3-642-11805-0
eBook Packages: Computer ScienceComputer Science (R0)