A mathematical evaluation and comparison of the space-efficiency of various 2D graphical representations of tree structures is presented. As part of the evaluation, a novel metric called the mean area exponent is introduced that quantifies the distribution of area across nodes in a tree representation, and that can be applied to a broad range of different representations of trees. Several representations are analyzed and compared by calculating their mean area exponent as well as the area they allocate to nodes and labels. Our analysis inspires a set of design guidelines as well as a few novel tree representations that are also presented.
ReingoldE.M.TilfordJ.S. (1981). Tidier drawings of trees. IEEE Transactions on Software Engineering7(2): 223–228.
2.
BuchheimC.JüngerM.LeipertS. (2002). Improving Walker's algorithm to run in linear time. In: KobourovS.G.GoodrichM.T. (eds.) Proceedings of Symposium on Graph Drawing (GD), Lecture Notes in Computer Science, Berlin, Germany: Springer-Verlag, pp. 344–353.
3.
JohnsonB.ShneidermanB. (1991) Tree-Maps: A Space-Filling Approach to the Visualization of Hierarchical Information Structures. In: NielsonG.M.RosenmblumL. (eds.) Proceedings of IEEE Visualization (VIS); Piscataway, NJ, USA: IEEE Computer Society Press, pp. 284–291.
4.
ShneidermanB. (1992). Tree visualization with tree-maps: 2-d space-filling approach. ACM Transactions on Graphics (TOG)11(1): 92–99.
5.
BrulsM.HuizingK.van WijkJ. J (2000) Squarified Treemaps. In: de LeeuwW.van LiereR. (eds.) Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization; Vienna, Berlin, Germany: Springer-Verlag, pp. 33–42.
6.
WattenbergM. (2005) A Note on Space-Filling Visualizations and Space-Filling Curves. In: StaskoJ.WardM. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis); Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 181–186.
7.
AndrewsK.HeideggerH. (1998) Information Slices: Visualising and Exploring Large Hierarchies Using Cascading, Semi-circular Discs. In: WillsG.DillJ. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis), Late Breaking Hot Topics, Los Alamitos, CA: IEEE Computer Society Press, pp. 9–12.
8.
StaskoJ.ZhangE. (2000) Focus + Context Display and Navigation Techniques for Enhancing Radial, Space-Filling Hierarchy Visualizations. In: RothS.F.KeimD.A. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis), Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 57–65.
9.
YangJ.WardM.O.RundensteinerE.A. (2002) InterRing: An Interactive Tool for Visually Navigating and Manipulating Hierarchical Structures. In: WongP.C.AndrewsK. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis), Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 77–84.
10.
HermanI.MelançonG.MarshallM.S. (January 2000). Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics (TVCG)6(1): 24–43.
11.
EadesP.D. (1992). Drawing free trees. Bulletin of the Institute for Combinatorics and its Applications5: 10–36.
12.
Di BattistaG.EadesP.TamassiaR.TollisI.G. (1999). Graph Drawing: Algorithms for the Visualization of Graphs. Englewood Cliffs, NJ: Prentice-Hall.
13.
BoardmanR. (2000). Bubble trees: The Visualization of Hierarchical Information Structures. In: TurnerT.SzwillusG. (eds.) Extended Abstracts of ACM Conference on Human Factors in Computing Systems (CHI); New York, USA: ACM Press, pp. 315–316.
14.
TeohS.T.MaK.-L. (2002). RINGS: A Technique for Visualizing Large Hierarchies. In: KobourovS.G.GoodrichM.T. (eds.) Proceedings of Graph Drawing (GD), Berlin, Germany: Springer-Verlag, pp. 268–275.
15.
BertinJ. (1967). Sémiologie graphique: Les diagrammes, Les réseaux, Les cartes. Paris: Éditions Gauthier-Villars, (2nd ed. 1973, English translation 1983).
16.
KnuthD.E. (1968) The Art of Computer Programming, volume I: Fundamental Algorithms. Reading, MA, USA: Addison-Wesley, pp. 309–310.
17.
EngelbartD.C.EnglishW.K. (1968) A research center for augmenting human intellect. (Video of public demonstration of NLS). Available from http://www.1968demo.org/.
18.
PlaisantC.GrosjeanJ.BedersonB.B. (2002) SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation. In: WongP.C.AndrewsK. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis);Los Alamitos, California, USA: IEEE Computer Society Press, pp. 57–64.
19.
NguyenQ.V.HuangM.L. (2002) A Space-Optimized Tree Visualization. In: WongP.C.AndrewsK. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis); Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 85–92.
20.
NguyenQ.V.HuangM.L. (2005). EncCon: An approach to constructing interactive visualization of large hierarchical data. Information Visualization4: 1–21.
21.
AnandV.HansenK.JianuR.RusuA. (2004) Area-Efficient Visualization of Web Data. In: ArabniaChatterjeeS. (eds.) Proceedings of International Conference on Internet Computing (IC), Vol. 1, Las Vegas, Nevada, USA: CSREA Press, pp. 83–89.
22.
GargA.GoodrichM.T.TamassiaR. (1996). Planar upward tree drawings with optimal area. International Journal of Computational Geometry and Applications6: 333–356.
23.
ShinC.-S.KimS.K.ChwaK.-Y. (1996) Area-Efficient Algorithms for Upward Straight-line Tree Drawings. In: CaiJ.-Y.WongC.K. (eds.) Proceedings of International Computing and Combinatorics (COCOON), Lecture Notes in Computer Science, Berlin, Germany: Springer-Verlag, pp. 106–116.
24.
PuloK.TakatsukaM. (2003) Inclusion Tree Layout Convention: An Empirical Investigation. In: PattisonT.ThomasB. (eds.) Proceedings of Asia-Pacific Symposium on Information Visualisation, Adelaide, Australia: Australian Computer Society, pp. 27–35.
25.
KakoulisK.G.TollisI.G. (1998) A unified Approach to Labeling Graphical Features. In: JanardanR. (ed.) Proceedings of Symposium on Computational Geometry, New York, USA: ACM Press, pp. 347–356.
26.
KoikeH.YoshiharaH. (eds.) (1993) Fractal Approaches for Visualizing Huge Hierarchies. Proceedings of IEEE Symposium on Visual Languages (VL), Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 55–60.
27.
CardS.K.NationD. (2002) Degree-of-Interest Trees: A Component of an Attention-Reactive User Interface. In: De MarsicoS.L.M.PanizziE. (eds.) Proceedings of ACM Advanced Visual Interfaces (AVI); New York, USA: ACM Press.
28.
BedersonB.B.HollanJ.D. (1994) Pad++: A Zooming Graphical Interface for Exploring Alternate Interface Physics. In: SzekelyP. (ed.) Proceedings of ACM Symposium on User Interface Software and Technology (UIST); New York, USA: ACM Press, pp. 17–26.
29.
ZhaoS.McGuffinM.J.ChignellM.H. (2005) Elastic Hierarchies: Combining Treemaps and Node-Link Diagrams. In: StaskoJ.WardM. (eds). Proceedings of IEEE Symposium on Information Visualization (InfoVis), Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 57–64.
30.
RobertsonG.G.MackinlayJ.D.CardS.K. (1991) Cone Trees: Animated 3D Visualizations of Hierarchical Information. In: RobertsonS.P.OlsonG.M.OlsonJ.S. (eds.) Proceedings of ACM 1991 Conference on Human Factors in Computing Systems (CHI); New York, USA: ACM Press, pp. 189–194.
31.
MuelderC.MaK.L. (2008) Rapid Graph Layout using Space Filling Curves. In: NorthC.CarpendaleS. (eds.) Proceedings of IEEE Symposium on Information Visualization (InfoVis); Los Alamitos, CA, USA: IEEE Computer Society Press.
32.
WangY.TeohS.T.MaK.-L. (2006) Evaluating the Effectiveness of Tree Visualization Systems for Knowledge Discovery. In: JorgeJ.A. (ed.) Proceedings of Eurographics/IEEE-VGTC Symposium on Visualization; Los Alamitos, CA, USA: IEEE Computer Society Press, pp. 67–74.
