Hyperbolic tree

Hyperbolic tree

In Web development jargon and information visualization, a hyperbolic tree (often shortened as hypertree) defines a visualization method for a graph inspired by hyperbolic geometry.

Displaying hierarchical data as a tree 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 2n, while the number of nodes for larger trees 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. [http://sigchi.org/chi95/Electronic/documnts/papers/jl_bdy.htm] . Hyperbolic trees employ hyperbolic space, 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 Poincare disk model 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 transformations of the space, bringing new nodes into focus and moving higher levels of the hierarchy out of view.

Although hyperbolic trees have been patented in the U.S. by Xerox, various Java & JavaScript implementations exist on the web.

ee also

*Hyperbolic geometry
*Tree (graph theory)
*Tree (data structure)

External links

* http://sigchi.org/chi95/Electronic/documnts/papers/jl_bdy.htm
* http://www.touchgraph.com/
* http://hypertree.woot.com.ar/
* http://xebece.sourceforge.net/screenshots
* [http://www.visualcomplexity.com/vc/ VisualComplexity] Images of alternative visualizations
* [http://www.touchgraph.com/ TouchGraph] Live demonstration

References


* Cite conference
last1 = Lamping | first1 = John
last2 = Rao | first2 = Ramana
last3 = Pirolli| first3 = Peter
title = A Focus+Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies
booktitle = Proc. ACM Conf. Human Factors in Computing Systems, CHI
pages = 401–408
publisher = ACM
year = 1995
url = http://citeseer.ist.psu.edu/lamping95focuscontext.html
contribution-url = http://sigchi.org/chi95/Electronic/documnts/papers/jl_bdy.htm

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Hyperbolic geometry — Lines through a given point P and asymptotic to line R. A triangle immersed in a saddle shape plane (a hyperbolic paraboloid), as well as two diverging ultraparall …   Wikipedia

  • Tree of life (biology) — See also Tree of life (disambiguation) for other meanings of the Tree of Life. Hillis plot Tree Of Life, based on completely sequenced genomes. Charles Darwin proposed that phylogeny, the evolutionary relatedness among species through time, was… …   Wikipedia

  • Hyperbolic group — In group theory, a hyperbolic group, also known as a word hyperbolic group, Gromov hyperbolic group, negatively curved group is a finitely generated group equipped with a word metric satisfying certain properties characteristic of hyperbolic… …   Wikipedia

  • Tree rotation — A tree rotation is an operation on a binary search tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. They are used to change the shape of the tree …   Wikipedia

  • Tree diagram — The term tree diagram is used in different ways in different disciplines. * In mathematics and statistical methods, a tree diagram is used to determine the probability of getting specific results where the possibilities are nested.… …   Wikipedia

  • Δ-hyperbolic space — In mathematics, a delta; hyperbolic space is a geodesic metric space in which every geodesic triangle is delta; thin .There are many equivalent definitions of delta; thin . A simple definition is as follows: pick three points and draw geodesic… …   Wikipedia

  • δ-hyperbolic space — In mathematics, a δ hyperbolic space is a geodesic metric space in which every geodesic triangle is δ thin. There are many equivalent definitions of δ thin . A simple definition is as follows: pick three points and draw geodesic lines between… …   Wikipedia

  • Real tree — A real tree, or an mathbb R tree, is a metric space ( M , d ) such thatfor any x , y in M there is a unique arc from x to y and this arc is a geodesic segment. Here by an arc from x to y we mean the image in M of a topological embedding f from an …   Wikipedia

  • Exponential tree — An exponential tree is almost identical to a binary search tree, with the exception that the dimension of the tree is not the same at all levels. In a normal binary search tree, each node has a dimension ( d ) of 1, and has 2 d children. In an… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”