| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Exploration of Networks using overview+detail with Constraint-based cooperative layout
November/December 2008 (vol. 14 no. 6)
pp. 1293-1300
A standard approach to large network visualization is to provide an overview of the network and a detailed view of a small component of the graph centred around a focal node. The user explores the network by changing the focal node in the detailed view or by changing the level of detail of a node or cluster. For scalability, fast force-based layout algorithms are used for the overview and the detailed view. However, using the same layout algorithm in both views is problematic since layout for the detailed view has different requirements to that in the overview. Here we present a model in which constrained graph layout algorithms are used for layout in the detailed view. This means the detailed view has high-quality layout including sophisticated edge routing and is customisable by the user who can add placement constraints on the layout. Scalability is still ensured since the slower layout techniques are only applied to the small subgraph shown in the detailed view. The main technical innovations are techniques to ensure that the overview and detailed view remain synchronized, and modifying constrained graph layout algorithms to support smooth, stable layout. The key innovation supporting stability are new dynamic graph layout algorithms that preserve the topology or structure of the network when the user changes the focus node or the level of detail by in situ semantic zooming. We have built a prototype tool and demonstrate its use in two application domains, UML class diagrams and biological networks.
[1] D. Archambault, T. Munzner, and D. Auber, Smashing peacocks further: Drawing quasi-trees from biconnected components. Trans. on Visualization and Computer Graphics, 12 (5): 13–820, 2006.
[2] C. Bachmaier, U. Brandes, and F. Schreiber, Handbook of Graph Drawing and Visualization, chapter Biological Networks. Chapman & Hall/CRC Press, 2008, to appear.
[3] B. B. Bederson and A. Boltman, Does animation help users build mental maps of spatial information. In Proc. 1999 IEEE Symp. on Information Visualization, pages 28–35. IEEE, 1999.
[4] D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.
[5] U. Brandes, V. Kääb, A. Löh, D. Wagner, and T. Willhalm, Dynamic WWW structures in 3D. Graph Algorithms and Applications, 4 (3): 183–191, 2000.
[6] S. S. Bridgeman, J. Fanto, A. Garg, R. Tamassia, and L. Vismara, InteractiveGiotto: An algorithm for interactive orthogonal graph drawing. In GD 1997: Revised Papers from the 5th Int. Symp. on Graph Drawing, pages 303–308. Springer, 1998.
[7] H. A. D. do Nascimento and P. Eades, User hints for directed graph drawing. In Revised Papers from the 9th Int. Symp. on Graph Drawing (GD '01), pages 205–219. Springer, 2002.
[8] T. Dwyer, Y. Koren, and K. Marriott, Drawing directed graphs using quadratic programming. IEEE Trans. on Visualization and Computer Graphics, 12 (4): 536–548, 2006.
[9] T. Dwyer, Y. Koren, and K. Marriott, IPSep-CoLa: An incremental procedure for separation constraint layout of graphs. IEEE Trans. on Visualization and Computer Graphics, 12 (5): 821–828, 2006.
[10] T. Dwyer, K. Marriott, and M. Wybrow, Integrating edge routing into force-directed layout. In Proc. 14th Intl. Symp. Graph Drawing (GD '06), volume 4372 of LNCS, pages 8–19. Springer, 2007.
[11] T. Dwyer, K. Marriott, and M. Wybrow, Topology preserving constrained graph layout. Technical Report 227, Monash University, 2008. http://www.csse.monash.edu.au/publications/ 2008tr-2008-227-full.pdf.
[12] P. Eades, R. F. Cohen, and M. L. Huang, Online animated graph drawing for web navigation. In Proc. 5th Int. Symp. on Graph Drawing (GD'97), pages 330–335, 1997.
[13] P. Eades and M. L. Huang, Navigating clustered graphs using force-directed methods. Graph Algorithms and Applications: Special Issue on Selected Papers from 1998 Symp. Graph Drawing, 4 (3): 157–181, 2000.
[14] M. Eiglsperger, S. P. Fekete, and G. W. Klau, Orthogonal Graph Drawing, pages 121–171. Springer, 2001.
[15] M. Eiglsperger, M. Siebenhaller, and M. Kaufmann, An efficient implementation of Sugiyama's algorithm for layered graph drawing. In Proc. 12th Int. Symp. on Graph Drawing (GD'04), volume 3383 of LNCS, pages 155–166, 2004.
[16] C. Friedrich and P. Eades, Graph drawing in motion. Graph Algorithms and Applications, 6 (3): 353–370, 2002.
[17] Y. Frishman and A. Tal, Online dynamic graph drawing. In Eurographics/IEEE-VGTC Symp. on Visualization. Eurographics Association, 2007.
[18] T. M. J. Fruchterman and E. M. Reingold, Graph drawing by force-directed placement. Software - Practice and Experience, 21 (11): 1129–1164, 1991.
[19] G. W. Furnas, Generalized fisheye views. In Proc. of CHI'86, pages 16–23. ACM Press, 1986.
[20] E. Gansner, Y. Koren, and S. North, Topological fisheye views for visualizing large graphs. In INFOVIS '04: Proc. IEEE Symp. on Information Visualization, pages 175–182. IEEE, 2004.
[21] E. Grafahrend-Belau, S. Weise, D. Koschützki, U. Scholz, B. H. Junker, and F. Schreiber, MetaCrop—a detailed database of crop plant metabolism. Nucleic Acids Research, 36: D954–958, 2008.
[22] S. Hachul and M. Jünger, Drawing large graphs with a potential-field-based multilevel algorithm. In Proc. 12th Int. Symp. on Graph Drawing (GD'04), volume 3383 of LNCS, pages 285–295. Springer, 2004.
[23] S. Hachul and M. Jünger, An experimental comparison of fast algorithms for drawing general large graphs. In Proc. 13th Int. Symp. on Graph Drawing (GD'05), LNCS, pages 235–250. Springer, 2005.
[24] W. He and K. Marriott, Constrained graph layout. Constraints, 3: 289–314, 1998.
[25] J. Heer and D. Boyd, Vizster: Visualizing online social networks. In INFOVIS '05: Proc. 2005 IEEE Symp. on Information Visualization, page 5. IEEE, 2005.
[26] Y. Koren, L. Carmel, and D. Harel, Ace: A fast multiscale eigenvectors computation for drawing huge graphs. In INFOVIS '02: Proc. IEEE Symp. on Information Visualization, page 137. IEEE, 2002.
[27] Y. K. Leung and M. D. Apperley, A review and taxonomy of distortion-oriented presentation techniques. ACM Trans. on Computer-Human Interaction, 1 (2): 126–160, 1994.
[28] K. Misue, P. Eades, W. Lai, and K. Sugiyama, Layout adjustment and the mental map. Journal of Visual Languages and Computing, 6 (2): 183–210, 1995.
[29] S. C. North and G. Woodhull, Online hierarchical graph drawing. In GD '01: Revised Papers from the 9th Int. Symp. on Graph Drawing, pages 232–246. Springer, 2002.
[30] A. Perer and B. Shneiderman, Balancing systematic and flexible exploration of social networks. Trans. on Visualization and Computer Graphics, 12 (5), 2006.
[31] C. Plaisant, J. Grosjean, and B. B. Bederson, Spacetree: Supporting exploration in large node link tree, design evolution and empirical evaluation. In INFOVIS, pages 57–, 2002.
[32] H. Purchase, J. Allder, and D. Carrington, Graph layout aesthetics in UML diagrams: User preferences. Journal of Graph Algorithms and Applications, 6 (3): 255–279, 2002.
[33] K. Ryall, J. Marks, and S. Shieber, An interactive constraint-based system for drawing graphs. In Proc. 10th Annual ACM Symp. on User Interface Software and Technology, pages 97–104. ACM Press, 1997.
[34] M. Sarkar and M. H. Brown, Graphical fisheye views of graphs. In Human Factors in Computing Systems, CHI'92 Conference Proc.: Striking A Balance, pages 83–91. ACM Press, 1992.
[35] K. Sugiyama, S. Tagawa, and M. Toda, Methods for visual understanding of hierarchical system structures. IEEE Trans. on Systems, Man and Cybernetics (SMC), 11 (2): 109–125, 1981.
[36] M. Tenenbaum and H. Pollard, Ordinary Differential Equations. Dover, 3rd edition, 1985.
[37] F. van Ham and J. J. van Wijk, Interactive visualization of small world graphs. In INFOVIS '04: Proc. IEEE Symp. on Information Visualization, pages 199–206. IEEE, 2004.
[38] C. Ware, Interacting with visualizations. In Information Visualization: Perception for Design, chapter 10, pages 317–350. Elsevier, 2nd edition, 2004.
[39] M. Wybrow, K. Marriott, and P. J. Stuckey, Incremental connector routing. In Proc. 13th Int. Symp. on Graph Drawing (GD'05), volume 3843 of LNCS, pages 446–457. Springer, 2006.
Index Terms:
Index Terms—Graph drawing, constraints, stress majorization, force directed algorithms, multidimensional scaling.
Citation:
Tim Dwyer, Kim Marriott, Falk Schreiber, Peter Stuckey, Michael Woodward, Michael Wybrow, "Exploration of Networks using overview+detail with Constraint-based cooperative layout," IEEE Transactions on Visualization and Computer Graphics, vol. 14, no. 6, pp. 1293-1300, Nov./Dec. 2008, doi:10.1109/TVCG.2008.130
