Succinct Greedy Graph Drawing in the Hyperbolic Plane

Details Succinct Greedy Graph Drawing in the Hyperbolic Plane Succinct Greedy Graph Drawing in the Hyperbolic Plane

2008-06-02

arxiv.org/abs/0806.0341v1

Computer Science

Computational Geometry

12 pages, 8 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Succinct Greedy Graph Drawing in the Hyperbolic Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Succinct Greedy Graph Drawing in the Hyperbolic Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Greedy Graph Drawing in the Hyperbolic Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-632564