Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data
|
A compound graph is a frequently encountered type of data set. Relations are given between items, and a hierarchy is defined on the items as well. We present a new method for visualizing such compound graphs. Our approach is based on visually bundling the adjacency edges, i.e., non-hierarchical edges, together. We realize this as follows. We assume that the hierarchy is shown via a standard tree visualization method. Next, we bend each adjacency edge, modeled as a B-spline curve, toward the polyline defined by the path via the inclusion edges from one node to another. This hierarchical bundling reduces visual clutter and also visualizes implicit adjacency edges between parent nodes that are the result of explicit adjacency edges between their respective child nodes. Furthermore, hierarchical edge bundling is a generic method which can be used in conjunction with existing tree visualization techniques. We illustrate our technique by providing example visualizations and discuss the results based on an informal evaluation provided by potential users of such visualizations.
[1] 741 B. A. Barsky, The Beta-Spline: A Local Representation based on Shape Parameters and Fundamental Geometric Measures. PhD thesis, University of Utah, 1981.
[2] G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[3] R. A. Becker, S. G. Eick, and A. R. Wilks, Visualizing Network Data. IEEE Transactions on Visualization and Computer Graphics, 1 (1): 16–28, 1995.
[4] F. Bertault and M. Miller, An Algorithm for Drawing Compound Graphs. In Proceedings of the 7th International Symposium on Graph Drawing (GD'99), pages 197–204, 1999.
[5] M. T. Dickerson, D. Eppstein, M. T. Goodrich, and J. Y. Meng, Confluent Drawings: Visualizing Non-Planar Diagrams in a Planar Way. In Proceedings of the 11th International Symposium on Graph Drawing (GD'03), pages 1–12, 2003.
[6] U. Dogrusoz, E. Giral, A. Cetintas, A. Civril, and E. Demir, A Compound Graph Layout Algorithm for Biological Pathways. In Proceedings of the 12th International Symposium on Graph Drawing (GD'04), pages 442–447, 2004.
[7] P. Eades, Drawing Free Trees. Bulletin of the Institute for Combinatorics and its Applications, 5 (2): 10–36, 1992.
[8] P. Eades, Q.-W. Feng, and X. Lin, Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs. In Proceedings of the 4th International Symposium on Graph Drawing (GD'96), pages 113–128, 1997.
[9] D. Eppstein, Delta-Confluent Drawings. In Proceedings of the 13th International Symposium on Graph Drawing (GD'05), pages 165–176, 2006.
[10] J.-D. Fekete, D. Wang, N. Dang, A. Aris, and C. Plaisant, Overlaying Graph Links on Treemaps. In Proceedings of the 2003 IEEE Symposium on Information Visualization (InfoVis'03), Poster Compendium, pages 82–83, 2003.
[11] Q.-W. Feng, Algorithms for Drawing Clustered Graphs. PhD thesis, University of Newcastle, 1997.
[12] T. M. J. Fruchterman and E. M. Reingold, Graph Drawing by Force-Directed Placement. Software — Practice and Experience, 21 (11): 1129–1164, 1991.
[13] M. Ghoniem, J.-D. Fekete, and P. Castagliola, A Comparison of the Readability of Graphs Using Node-Link and Matrix-Based Representations. In Proceedings of the 2004 IEEE Symposium on Information Visualization (InfoVis'04), pages 17–24, 2004.
[14] D. Harel and Y. Koren, A Fast Multi-Scale Method for Drawing Large Graphs. Journal of Graph Algorithms and Applications, 6 (3): 179–202, 2002.
[15] I. Herman, G. Melançon, and M. S. Marshall, Graph Visualization and Navigation in Information Visualization: A Survey. IEEE Transactions on Visualization and Computer Graphics, 6 (1): 24–43, 2000.
[16] M. Kaufmann and D. Wagner, Drawing Graphs: Methods and Models. Springer, 2001.
[17] Y. Koren, L. Carmel, and D. Harel, Drawing Huge Graphs by Algebraic Multigrid Optimization. Multiscale Modeling and Simulation, 1 (4): 645–673, 2003.
[18] J. Lamping and R. Rao, The Hyperbolic Browser: A Focus + Context Technique for Visualizing Large Hierarchies. Journal of Visual Languages and Computing, 7 (1): 33–55, 1996.
[19] T. Munzner, H3: Laying out Large Directed Graphs in 3D Hyperbolic Space. In Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis'97), pages 2–10, 1997.
[20] P. Neumann, S. Schlechtweg, and M. S. T. Carpendale, ArcTrees: Visualizing Relations in Hierarchical Data. In Proceedings of the 2005 Eurographics / IEEE VGTC Symposium on Visualization (EuroVis'05), pages 53–60, 2005.
[21] Q. V. Nguyen and M. L. Huang, A Space-Optimized Tree Visualization. In Proceedings of the 2002 IEEE Symposium on Information Visualization (InfoVis'02), pages 85–92, 2002.
[22] D. Phan, L. Xiao, R. Yeh, P. Hanrahan, and T. Winograd, Flow Map Layout. In Proceedings of the 2005 IEEE Symposium on Information Visualization (InfoVis'05), pages 219–224, 2005.
[23] M. Raitner, Visual Navigation of Compound Graphs. In Proceedings of the 12th International Symposium on Graph Drawing (GD'04), pages 403–413, 2004.
[24] E. M. Reingold and J. S. Tilford, Tidier Drawings of Trees. IEEE Transactions on Software Engineering, 7 (2): 223–228, 1981.
[25] Rigi: A Visual Tool for Understanding Legacy Systems. University of Victoria. http://www.rigi.csc.uvic.ca.
[26] G. G. Robertson, J. D. Mackinlay, and S. K. Card, Cone Trees: Animated 3D Visualizations of Hierarchical Information. In Proceedings of the 1991 SIGCHI Conference on Human Factors in Computing Systems (CHI'91), pages 189–194, 1991.
[27] B. Shneiderman, Tree Visualization with Tree-Maps: 2-d Space-Filling Approach. ACM Transactions on Graphics (TOG), 11 (1): 92–99, 1992.
[28] M.-A. D. Storey and H. A. Müller, Manipulating and Documenting Software Structures using SHriMP Views. In Proceedings of the 1995 International Conference on Software Maintenance (ICSM'95), pages 275–284, 1995.
[29] K. Sugiyama and K. Misue, Visualization of Structural Information: Automatic Drawing of Compound Digraphs. IEEE Transactions on Systems, Man, and Cybernetics, 21 (4): 876–892, 1991.
[30] F. van Ham, Using Multilevel Call Matrices in Large Software Projects. In Proceedings of the 2003 IEEE Symposium on Information Visualization (InfoVis'03), pages 227–232, 2003.
[31] N. Wong, S. Carpendale, and S. Greenberg, EdgeLens: An Interactive Method for Managing Edge Congestion in Graphs. In Proceedings of the 2003 IEEE Symposium on Information Visualization (InfoVis'03), pages 51–58, 2003.
[32] S. Zhao, M. J. McGuffin, and M. H. Chignell, Elastic Hierarchies: Combining Treemaps and Node-Link Diagrams. In Proceedings of the 2005 IEEE Symposium on Information Visualization (InfoVis'05), pages 57–64, 2005.
[33] J. Ziegler, C. Kunz, and V. Botsch, Matrix Browser: Visualizing and Exploring Large Networked Information Spaces. In Extended Abstracts of the 2002 SIGCHI Conference on Human Factors in Computing Systems (CHI'02), pages 602–603, 2002.
Index Terms:
Network visualization, edge bundling, edge aggregation, edge concentration, curves, graph visualization, tree visualization, node-link diagrams, hierarchies, treemaps.
Citation:
Danny Holten, "Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 741-748, Sept. 2006, doi:10.1109/TVCG.2006.147
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb