Geographic Routing Using Hyperbolic Space



Bobby Kleinberg
Cornell University

Monday  February 19, 2006
4:00 PM, 5130 Upson Hall



In a greedy routing scheme, nodes of a network are assigned virtual coordinates belonging to a metric space, and packets are routed to their destination by a sequence of hops in which the node currently holding the packet delivers it to the neighbor who is closest to the destination. Such routing schemes are used extensively in wireless sensor networks, but it is tricky to design greedy routing schemes which guarantee successful delivery of packets for every source-destination pair; when the assignment of virtual coordinates satisfies this property, we call it a "greedy embedding". A conjecture of Papadimitriou and Ratajczak asserts that every 3-connected planar graph has a greedy embedding in the Euclidean plane. In this talk, we will see that the conjecture becomes true --- and, moreover, EVERY finite connected graph has a greedy embedding in the plane --- if we shift from the standard Euclidean metric to the hyperbolic metric. Familiarity with hyperbolic geometry will not be assumed; indeed much of this talk will be a brief tour through the history and properties of the hyperbolic plane.