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....
Dear David,
ReplyDeleteYou might like to know about a dramatic new framework for this illustrious subject. It is based on Rational Trigonometry (see my YouTube series called `Wildtrig') and is laid out from first principles in the paper `Universal Hyperbolic Geometry I: Trigonometry' on the ArXiV at
http://arxiv.org/abs/0909.1377
Roughly, we extend the Beltrami Klein model to the whole projective space, introduce quadrance and spread to replace distance angle, and work over a general field. Most of the usual theorems become much simpler and more elegant, and there are a raft of new theorems, often remarkable.
Norman Wildberger (Assoc Prof UNSW)