2016/09/14 by Leone, Pierre, Samarasinghe, Kasun
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1609.04173
Geographic routing is a routing paradigm, which uses geographic coordinates of network nodes to determine routes. Greedy routing, the simplest form of geographic routing forwards a packet to the closest neighbor towards the destination. A greedy embedding is a embedding of a graph on a geometric space such that greedy routing always guarantees delivery. A Schnyder drawing is a classical way to draw a planar graph. In this manuscript, we show that every Schnyder drawing is a greedy embedding, based on a generalized definition of greedy routing.