This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Exploring Multiple Trees through DAG Representations
November/December 2007 (vol. 13 no. 6)
pp. 1294-1301
Martin Graham, IEEE Computer Society
We present a Directed Acyclic Graph visualisation designed to allow interaction with a set of multiple classification trees, specifically to find overlaps and differences between groups of trees and individual trees. The work is motivated by the need to find a representation for multiple trees that has the space-saving property of a general graph representation and the intuitive parent-child direction cues present in individual representation of trees. Using example taxonomic data sets, we describe augmentations to the common barycenter DAG layout method that reveal shared sets of child nodes between common parents in a clearer manner. Other interactions such as displaying the multiple ancestor paths of a node when it occurs in several trees, and revealing intersecting sibling sets within the context of a single DAG representation are also discussed.

[1] M. Graham, J. B. Kennedy, and C. Hand, "A Comparison of Set-Based and Graph-Based Visualisations of Overlapping Classification Hierarchies," In, V. D. Gesú, S. Levialdi, and L. Tarantino, editors, Proc. ACM AVI (Palermo, Italy, May 23–26, 2000), pages 41–50. ACM Press.
[2] E. M. Reingold and J. S. Tilford, "Tidier drawing of trees," IEEE Transactions on Software Engineering, vol. 7, no. 2, pp. 223–228, March 1981.
[3] N. H. F. Beebe, "A Bibliography of Tree Drawing Algorithms." Salt Lake City: Department of Mathematics, University of Utah, 2006, pp. 22.
[4] C. Plaisant, J. Grosjean, and B. B. Bederson, "SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation," In Proc. IEEE InfoVis (Boston, Massachusetts, USA, October 28–29, 2002), pages 57–64. IEEE Computer Society.
[5] B. Johnson and B. Shneiderman, "Treemaps: A Space-Filling approach to the visualization of hierarchical information structures," In Proc. IEEE Visualization (San Diego, California, USA, Oct 22–25, 1991), pages 284–291. IEEE Computer Society Press.
[6] W. Wang, H. Wang, G. Dai, and H. Wang, "Visualization of Large Hierarchical Data by Circle Packing," In Proc. ACM CHI (Montréal, Québec, Canada, April 22–28, 2006), pages 517–520. ACM Press.
[7] M. Sifer, "Filter co-ordinations for exploring multi-dimensional data," Journal of Visual Languages and Computing, vol. 17, no. 2, pp. 107–125, 2006.
[8] J. Stasko and E. Zhang, "Focus+Context Display and Navigation Techniques for Enhancing Radial, Space-Filling Hierarchy Visualizations," In Proc. IEEE InfoVis (Salt Lake City, Utah, USA, October 9–10, 2000), pages 57–65. IEEE Computer Society Press.
[9] G. G. Robertson, J. D. Mackinlay, and S. K. Card, "Cone Trees: Animated 3D Visualizations of Hierarchical Information," In Proc. ACM CHI: Human Factors in Computing Systems (New Orleans, Louisiana, USA, April 27 – May 2, 1991), pages 189–194. ACM Press.
[10] T. Bladh, D. A. Carr, and J. Scholl, "Extending Tree-Maps to Three Dimensions: A Comparative Study," In, M. Masoodian, S. Jones, and B. Rogers, editors, Proc. 6th Asia-Pacific Conference on Computer-Human Interaction (Rotorua, New Zealand, June 29 – July 2, 2004), pages 50–59. Springer-Verlag.
[11] F. van Ham and J. J. van Wijk, "Beamtrees: Compact Visualization of Large Hierarchies," In Proc. IEEE InfoVis (Boston, Massachussets, USA, October 28–29, 2002), pages 93–100. IEEE Computer Society Press.
[12] S. Zhao, M. J. McGuffin, and M. H. Chignell, "Elastic Hierarchies: Combining Treemaps and Node-Link Diagrams," In Proc. IEEE InfoVis (Minneapolis, Minnesota, USA, October 23–25, 2005), pages 57–64. IEEE Computer Society Press.
[13] A. Kobsa, "User Experiments with Tree Visualization Systems," In Proc. IEEE InfoVis (Austin, Texas, USA, September 10–12, 2004), pages 9–16. IEEE Computer Society Press.
[14] E. R. Tufte, The Visual Display of Quantitative Information. Cheshire, Connecticut: Graphics Press, 1983.
[15] T. Munzner, F. Guimbretière, S. Tasiran, L. Zhang, and Y. Zhou, "TreeJuxtaposer: Scalable Tree Comparison using Focus+Context with Guaranteed Visibility," ACM Transactions on Graphics, vol. 22, no. 3, pp. 453–462, July 2003.
[16] M. Graham, J. Kennedy, and L. Downey, "Visual Comparison and Exploration of Natural History Collections," In, A. Celentano and P. Mussio, editors, Proc. Advanced Visual Interfaces (AVI) (Venice, Italy, May 23–26, 2006), pages 310–313. ACM Press.
[17] E. H. Chi, J. Pitkow, J. Mackinlay, P. Pirolli, R. Gossweiler, and S. K. Card, "Visualizing the Evolution of Web Ecologies," In Proc. ACM CHI (Los Angeles, California, USA, April 18–23, 1998), pages 400–407. ACM Press.
[18] K. Wittenburg, D. Das, W. Hill, and L. Stead, "Group Asynchronous Browsing on the World Wide Web," In Proc. Fourth International World Wide Web Conference (Boston, Massachusetts, USA, December 11–14, 1995), pages 51–62.
[19] D. R. Morse, N. Ytow, and D. M. Roberts, "Comparison of multiple taxonomic hierarchies using TaxoNote," In Proc. IEEE InfoVis Poster Compendium (Seattle, Washington, USA, 19–21 October, 2003), pages 126–127. IEEE Computer Society Press.
[20] M. Ghoniem and J.-D. Fekete, "Animating Treemaps," In Proc. 18th HCIL Symposium - Workshop on Treemap Implementations and Applications (University of Maryland, College Park, Maryland, USA, May 31, 2001).
[21] K. Wittenburg and E. Sigman, "Visual Focusing and Transition Techniques in a Treeviewer for Web Information Access," In Proc. Visual Languages (Capri, Italy, September 23–26, 1997), pages 20–27. IEEE Computer Society Press.
[22] J. Y. Hong, J. D'Andries, M. Richman, and M. Westfall, "Zoomology: Comparing Two Large Hierarchical Trees," In Proc. IEEE InfoVis Poster Compendium (Seattle, Washington, USA, 19–21 October, 2003), pages 120–121. IEEE Computer Society Press.
[23] G. W. Furnas and J. Zacks, "Multitrees: Enriching and Reusing Hierarchical Structure," In Proc. ACM CHI (Boston, Massachusetts, USA, April 24–28, 1994), pages 330–336. ACM Press.
[24] T. Dwyer and F. Schreiber, "Optimal Leaf Ordering for Two and a Half Dimensional Phylogenetic Tree Visualisation," In, N. Churcher and C. Churcher, editors, Proc. Australasian Symposium on Information Visualisation (Dunedin, New Zealand, January 23–24, 2004), pages 109–115. Australian Computer Society.
[25] D. M. Hillis, T. A. Heath, and K. St. John, "Analysis and Visualization of Tree Space," Systematic Biology, vol. 54, no. 3, pp. 471–482, 2005.
[26] Information Visualization Benchmarks Repository, "InfoVis 2003 Contest - Visualization and PairWise Comparison of Trees," http://www.cs.umd.edu/hcil/InfovisRepository contest-2003/, Last accessed March28, 2007.
[27] E. A. Wernert, D. K. Berry, J. N. Huffman, and C. A. Stewart, "Tree3D - A System for Temporal and Comparative Analysis of Phylogenetic Trees," In Proc. IEEE InfoVis Poster Compendium (Seattle, Washington, USA, October 19–21, 2003), pages 114–115. IEEE Computer Society Press.
[28] M. McGuffin and M. C. Schraefel, "A Comparison of Hyperstructures: Zzstructures, mSpaces, and Polyarchies," In Proc. ACM Hypertext (Santa Cruz, California, USA, August 9–13, 2004), pages 153–162. ACM Press.
[29] G. Melançon and I. Herman, "DAG Drawing from an Information Visualization Perspective," In, R. van Liere and W. de Leeuw, editors, Proc. Eurographics/IEEE TCVG Symposium on Visualization (VisSym) (Amsterdam, The Netherlands, May 29–31, 2000), pages 3–12. Springer-Verlag.
[30] G. Robertson, K. Cameron, M. Czerwinski, and D. Robbins, "Animated visualization of multiple intersecting hierarchies," Information Visualization, vol. 1, no. 1, pp. 50–65, March 2002.
[31] M. Graham, "Visualising Multiple Overlapping Classification Hierarchies," PhD Dissertation, School of Computing, Napier University, Edinburgh, UK, 2001.
[32] P. Eades and N. C. Wormald, "Edge crossings in drawings of bipartite graphs," Algorithmica, vol. 11, no. 4, pp. 379–403, 1994.
[33] W. Barth, P. Mutzel, and M. Jünger, "Simple and Efficient Bilayer Cross Counting," Journal of Graph Algorithms and Applications, vol. 8, no. 2, pp. 179–194, 2004.
[34] K. Sugiyama, S. Tagawa, and M. Toda, "Methods for visual understanding of hierarchical systems," IEEE Transactions on Systems, Man and Cybernetics, vol. 11, no. 2, pp. 109–125, 1981.
[35] R. Martí and M. Laguna, "Heuristics and meta-heuristics for 2-layer straight line crossing minimization," Discrete Applied Mathematics, vol. 127, no. 3, pp. 665–678, May1 2003.
[36] T. A. Feo and M. G. C. Resende, "Greedy randomized adaptive search procedures," Journal of Global Optimization, vol. 6, no. 2, pp. 109–133, March 1995.
[37] F. Glover and F. Laguna, Tabu Search. Norwell, Massachusetts, USA: Kluwer Academic Publishers, 1997.
[38] E. R. Gansner, S. C. North, and K. P. Vo, "DAG— A Program that Draws Directed Graphs," Software, Practice and Experience, vol. 18, no. 11, pp. 1047–1062, November 1988.
[39] E. Catmull and R. Rom, "A class of local interpolating splines," - Computer Aided Geometric Design, R. E. Barnhill and R. F. Riesenfeld, eds., New York: Academic Press, pp. 317–326, 1974.
[40] M. Wattenberg, "Visual Exploration of Multivariate Graphs," In Proc. ACM CHI (Montréal, Québec, Canada, April 22–28, 2006), pages 811–819. ACM Press.
[41] P. Riehmann, M. Hanfler, and B. Froehlich, "Interactive Sankey Diagrams," In Proc. IEEE Symposium on Information Visualization (Minneapolis, Minnesota, USA, October 23–25, 2005), pages 233–240. IEEE Computer Society Press.
[42] J. Nielsen, "Guerrila HCI: Using Discount Usability Engineering to Penetrate the Intimidation Barrier," - Cost-Justifying Usability, 1st ed, R. G. Bias and D. J. Mayhew, eds.: Academic Press Professional, pp. 245–272, Chapter 11, 1994.

Index Terms:
Multiple trees, Directed Acyclic Graph.
Citation:
Martin Graham, Jessie Kennedy, "Exploring Multiple Trees through DAG Representations," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 6, pp. 1294-1301, Nov.-Dec. 2007, doi:10.1109/TVCG.2007.70556
Usage of this product signifies your acceptance of the Terms of Use.