Succinct greedy drawings do not always exist. (English) Zbl 1244.05154
Summary: A greedy drawing is a graph drawing containing a distance-decreasing path for every pair of nodes. A path \((v_{0},v_{1},\dots ,v_{m})\) is distance-decreasing if \(d(v_{i},v_{m}) < d(v_{i-1},v_{m})\), for \(i = 1,\dots ,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.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
References:
| [1] | Angelini, An algorithm to construct greedy drawings of triangulations, J Graph Algorithms Appl 14 pp 19– (2010) · Zbl 1194.05108 · doi:10.7155/jgaa.00197 |
| [2] | Dhandapani, Greedy drawings of triangulations, Discrete Comput Geom 43 pp 375– (2010) · Zbl 1213.05180 · doi:10.1007/s00454-009-9235-6 |
| [3] | Di Battista, Proximity drawability: A survey, Proc 2nd Symp Graph Drawing, Lecture Notes in Computer Science 894 pp 328– (1995) |
| [4] | Di Battista, Area requirement and symmetry display of planar upward drawings, Discrete Comput Geom 7 pp 381– (1992) · Zbl 0757.05055 · doi:10.1007/BF02187850 |
| [5] | Eppstein, Succinct greedy graph drawing in the hyperbolic plane, Proc 16th Symp Graph Drawing, Lecture Notes in Computer Science 5417 pp 14– (2008) · Zbl 1213.68444 |
| [6] | Ghosh, On convex greedy embedding conjecture for 3-connected planar graphs, Proc. 17th Symp Fundam Computation Theory, Lecture Notes in Computer Science 5699 pp 145– (2009) · Zbl 1252.68211 |
| [7] | Goodrich, Succinct greedy geometric routing in the euclidean plane, Proc. 20th Int Symp Algorithms Computation, Lecture Notes in Computer Science 5878 pp 781– (2009) · Zbl 1273.68392 |
| [8] | He, Succinct convex greedy drawing of 3-connected plane graphs, Proc. ACM-SIAM Symp Discr Algorithms pp 1477– (2011) · Zbl 1374.68352 |
| [9] | Kaufmann, Polynomial area bounds for MST embeddings of trees, Comp Geom 44 pp 529– (2011) · Zbl 1234.05068 · doi:10.1016/j.comgeo.2011.05.005 |
| [10] | Kleinberg, Geographic routing using hyperbolic space, Proc. 26th Ann IEEE Conference Comput Commun pp 1902– (2007) |
| [11] | Knaster, Ein beweis des fixpunktsatzes fur n dimensionale simplexe, Fundam Math 14 pp 132– (1929) · JFM 55.0972.01 |
| [12] | Leighton, Some results on greedy embeddings in metric spaces, Discrete Comput Geom 44 pp 686– (2010) · Zbl 1230.05269 · doi:10.1007/s00454-009-9227-6 |
| [13] | Monma, Transitions in geometric minimum spanning trees, Discrete Comput Geom 8 pp 265– (1992) · Zbl 0764.05022 · doi:10.1007/BF02293049 |
| [14] | Papadimitriou, Lecture Notes in Computer Science 3121, in: On a conjecture related to geometric routing, Proc 1st Algorithmic Aspects Wireless Sensor Networks pp 9– (2004) · doi:10.1007/978-3-540-27820-7_3 |
| [15] | Papadimitriou, On a conjecture related to geometric routing, Theor Comput Sci 344 pp 3– (2005) · Zbl 1079.68078 · doi:10.1016/j.tcs.2005.06.022 |
| [16] | Penna, Proximity drawings in polynomial area and volume, Comput Geom 29 pp 91– (2004) · Zbl 1050.05039 · doi:10.1016/j.comgeo.2004.03.015 |
| [17] | Rao, Proc. 9th International Conference On Mobile Computing and Networking, in: Geographic routing without location information pp 96– (2003) |
| [18] | Schnyder, Proc. 1st Annual ACM-SIAM Symposium Discrete on Algorithms, in: Embedding planar graphs on the grid pp 138– (1990) |
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.
