Tuesday, March 30, 2004

Hyperbolic Geometry And Graph Visualization

Just attended a talk (our regular Tuesday "cookie talk") on hyperbolic geometry for graph visualization, by Paul Burchard.

One of the problems that has plagued people who draw graphs is the fact that Euclidean spaces are not ideally suited for representing graphs. First of all, if your graph isn't planar, you have crossings of various kinds, and then if the graph has lots of edges, drawing the interconnects can make rendering a nightmare.

An approach proposed by Munzner and Burchard suggests the use of hyperbolic geometry to render graphs, instead of Euclidean geometry. Hyperbolic spaces drop the parallel postulate, replacing it by the following:

For any infinite straight line L and any point P not on it, there are many other infinitely extending straight lines that pass through P and which do not intersect L.

-- From MathWorld


This has many consequences, among them the fact that the sum of angles of a triangle is no longer 180 degrees (it is less). An interesting metric property is now that the circumference of a circle of "radius" R has length roughly e^R, instead of R for Euclidean spaces.

What this implies is that there is "more space" in a hyperbolic geometry to represents points that are not too far away from you. A graph may have many points close to it (an exponential number in many cases), and so a hyperbolic space provides the real estate needed to render such graphs.

There are numerous references on hyperbolic geometry on the web (and many applets that explain what it means to draw a line, triangle, circle etc in hyperbolic space). The Geometry Junkyard has a good collection.

An interesting question is: can we embed an arbitrary metric space in a hyperbolic space with no distortion in edge lengths ? the exponential blowup in the volume of a ball seems to suggest that this is possible....
Post a Comment

Disqus for The Geomblog