## October 17, Fall 2008: Theory Seminar

### 1:00pm in 253 ICS

# Succinct Greedy Graph Drawing in the Hyperbolic Plane

##
Prof. Michael Goodrich, UC Irvine

Abstract: We describe an efficient method for drawing any n-vertex
simple graph G in the hyperbolic plane. Our algorithm produces greedy
drawings, which support greedy geometric routing, so that a message M
between any pair of vertices may be routed geometrically, simply by
having each vertex that receives M pass it along to any neighbor
that is closer in the hyperbolic metric to the message's eventual
destination. More importantly, for networking applications, our
algorithm produces succinct drawings, in that each of the vertex
positions in one of our embeddings can be represented using O(log n)
bits and the calculation of which neighbor to send a message to may
be performed efficiently using these representations. These properties
are useful, for example, for routing in sensor networks, where storage
and bandwidth are limited.

Joint work with David Eppstein.