Succinct Greedy Drawings Do Not Always ExistDi 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 2225, 2009 , pp. 171182(Official URL: http://dx.doi.org/10.1007/9783642118050_17). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_17
AbstractA greedy drawing is a graph drawing containing a distancedecreasing path for every pair of nodes. A path (v0 , v1 , . . . , vm ) is distancedecreasing 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 greedydrawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits.
Actions (login required)
