HyperbolicTree
Encyclopedia
In Web development
jargon
and information visualization
, a hyperbolic tree (often shortened as hypertree) defines a graph drawing
method 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. 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 as well as C++ & OpenGL.
Web development
Web development is a broad term for the work involved in developing a web site for the Internet or an intranet . This can include web design, web content development, client liaison, client-side/server-side scripting, web server and network security configuration, and e-commerce development...
jargon
Jargon
Jargon is terminology which is especially defined in relationship to a specific activity, profession, group, or event. The philosophe Condillac observed in 1782 that "Every science requires a special language because every science has its own ideas." As a rationalist member of the Enlightenment he...
and information visualization
Visualization (graphic)
Visualization is any technique for creating images, diagrams, or animations to communicate a message. Visualization through visual imagery has been an effective way to communicate both abstract and concrete ideas since the dawn of man...
, a hyperbolic tree (often shortened as hypertree) defines a graph drawing
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, cartography, and bioinformatics...
method inspired by hyperbolic geometry
Hyperbolic geometry
In mathematics, hyperbolic geometry is a non-Euclidean geometry, meaning that the parallel postulate of Euclidean geometry is replaced...
.
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
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. Hyperbolic trees employ hyperbolic space
Hyperbolic geometry
In mathematics, hyperbolic geometry is a non-Euclidean geometry, meaning that the parallel postulate of Euclidean geometry is replaced...
, 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
Poincaré disk model
In geometry, the Poincaré disk model, also called the conformal disk model, is a model of n-dimensional hyperbolic geometry in which the points of the geometry are in an n-dimensional disk, or unit ball, and the straight lines of the hyperbolic geometry are segments of circles contained in the disk...
model of hyperbolic geometry, though the Klein-Beltrami
Klein model
In geometry, the Beltrami–Klein model, also called the projective model, Klein disk model, and the Cayley–Klein model, is a model of n-dimensional hyperbolic geometry in which points are represented by the points in the interior of the n-dimensional unit ball and lines are represented by the...
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 as well as C++ & OpenGL.
See also
- Hyperbolic geometryHyperbolic geometryIn mathematics, hyperbolic geometry is a non-Euclidean geometry, meaning that the parallel postulate of Euclidean geometry is replaced...
- Information visualizationInformation visualizationInformation visualization is the interdisciplinary study of "the visual representation of large-scale collections of non-numerical information, such as files and lines of code in software systems, library and bibliographic databases, networks of relations on the internet, and so forth".- Overview...
- Tree (graph theory)Tree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
- Tree (data structure)Tree (data structure)In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
- Radial treeRadial treeA radial tree, or "radial map", is a method of displaying a tree structure in a way that expands outwards, radially. It is one of many ways to visually display a tree., with examples extending back to the early 20th century...
- is also circular, but uses linear geometry.
External links
- http://sigchi.org/chi95/Electronic/documnts/papers/jl_bdy.htm
- JavaScript InfoVis Toolkit has an interactive Hyperbolic Tree visualization.
- The Green Tree of Life - Tree of lifeTree of lifeThe concept of a tree of life, a many-branched tree illustrating the idea that all life on earth is related, has been used in science , religion, philosophy, mythology, and other areas...
- University of California at Berkeley and Jepson Herbaria - http://xebece.sourceforge.net/screenshots
- http://hypergraph.sourceforge.net/ Applet, supports trees as well as generic graphs
- VisualComplexity Images of alternative visualizations
- TouchGraph Live demonstration
- Comprehensive survey and bibliography of Tree Visualization techniques