A hyperbolic tree (often shortened as hypertree) is an

information visualization Information is an abstract concept that refers to that which has the power to inform. At the most fundamental level information pertains to the interpretation of that which may be sensed. Any natural process that is not completely random, ...

and

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, ...

method inspired by

hyperbolic geometry In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P ...

Displaying hierarchical data as a

tree In botany, a tree is a perennial plant with an elongated Plant stem, stem, or trunk (botany), trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondar ...

suffers from visual clutter as the number of nodes per level can grow exponentially. For a simple binary tree, the maximum number of nodes at a level ''n'' is 2^''n'', while the number of nodes for trees with more branching grows much more quickly. Drawing the tree as a node-link diagram thus requires exponential amounts of space to be displayed. One approach is to use a ''hyperbolic tree'', first introduced by Lamping et al. Hyperbolic trees employ

hyperbolic space In mathematics, hyperbolic space of dimension n is the unique simply connected, n-dimensional Riemannian manifold of constant sectional curvature equal to -1. It is homogeneous, and satisfies the stronger property of being a symmetric space. The ...

, which intrinsically has "more room" than Euclidean space. For instance, linearly increasing the radius of a circle in Euclidean space increases its circumference linearly, while the same circle in hyperbolic space would have its circumference increase exponentially. Exploiting this property allows laying out the tree in hyperbolic space in an uncluttered manner: placing a node far enough from its parent gives the node almost the same amount of space as its parent for laying out its own children. Displaying a hyperbolic tree commonly utilizes the

Poincaré disk model In geometry, the Poincaré disk model, also called the conformal disk model, is a model of 2-dimensional hyperbolic geometry in which all points are inside the unit disk, and straight lines are either circular arcs contained within the disk t ...

of hyperbolic geometry, though the Klein-Beltrami model can also be used. Both display the entire hyperbolic plane within a unit disk, making the entire tree visible at once. The unit disk gives a fish-eye lens view of the plane, giving more emphasis to nodes which are in focus and displaying nodes further out of focus closer to the boundary of the disk. Traversing the hyperbolic tree requires

Möbius transformation In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form f(z) = \frac of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad' ...

s of the space, bringing new nodes into focus and moving higher levels of the hierarchy out of view. Hyperbolic trees were patented in the U.S. by Xerox in 1996, but the patent has since expired.

References

External links

d3-hypertree
– HTML5 Hyperbolic tree implementation, MIT licensed
Hyperbolic Tree of life
– Open source tree of life visualisation using Open Tree of Life data set

–

Tree of life The tree of life is a fundamental archetype in many of the world's mythological, religious, and philosophical traditions. It is closely related to the concept of the sacred tree.Giovino, Mariana (2007). ''The Assyrian Sacred Tree: A Histor ...

– University of California at Berkeley and Jepson Herbaria
Tree of life
Similar to the above, but with pictures
RogueViz
supports hyperbolic trees. {{DEFAULTSORT:Hyperbolic Tree Hyperbolic geometry Graph drawing Trees (data structures)

See also

References

External links