Succinct Greedy Drawings Do Not Always Exist

摘要

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.