On succinct greedy drawings of plane triangulations and 3-connected plane graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R ² (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3-14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686-705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. In this paper, we show that the classical Schnyder drawing in R ² of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R ² that is equivalent to Euclidean metric D _E (u,v) (in the sense that D-{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D-{E}(u,v)). The drawing uses two integer coordinates between 0 and 2n-5, which can be represented by logn bits. We also show that the classical Schnyder drawing in R ² of 3-connected plane graphs is weakly greedy with respect to the same metric function H(â̂ -,â̂ -). The drawing uses two integer coordinates between 0 and f (where f is the number of internal faces of G).