Succinct greedy drawings do not always exist
Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati · Networks · 2012
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. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012