| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected Components
September-October 2006 (vol. 12 no. 5)
pp. 813-820
Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component. That tree is drawn with a new area-aware variant of a tree drawing algorithm that handles high-degree nodes gracefully, at the cost of allowing edge-node overlaps. SPF performs an order of magnitude faster than the best previous approaches, while producing drawings of commensurate or improved quality.
[1] 813 A. T. Adai, S. V. Date, S. Wieland, and E. M. Marcotte, LGL: Creating a map of protein function with an algorithm for visualizing very large biological networks. Journal of Molecular Biology, 340 (1): 179–190, June 2004.[2] D. Archambault, T. Munzner, and D. Auber, TopoLayout: Graph layout by topological features. In IEEE Information Visualization Posters Compendium (InfoVis'05), pages 3–4, 2005.[3] D. Archambault, T. Munzner, and D. Auber, TopoLayout: Graph layout by topological features. Trans. on Visualization and Computer Graphics, 2006. to appear.[4] D. Auber, Tulip : A huge graph visualization framework. In P. Mutzel and M. Jünger, editors, Graph Drawing Software, Mathematics and Visualization, pages 105–126. Springer-Verlag, 2003.[5] S. Baase and A. V. Gelder, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley, 3rd edition, 2000.[6] F. Boutin, J. Thièvre, and M. Hascoët, Focus-based filtering + clustering technique for power-law networks with small world phenomenon. In Proc. of the Conference on Visualization and Data Analysis (VDA '06), 2006.[7] C. Buchheim, M. Jünger, and S. Leipert, Improving Walker's algorithm to run in linear time. In Proc. Graph Drawing (GD '02), volume 2528 of LNCS, pages 344–353. Springer, Berlin, 2002.[8] B. Cheswick, H. Burch, and S. Branigan, Mapping and visualizing the Internet. In Proc. USENIX, 2000.[9] H. S. M. Coxeter, Introduction to Geometry. Wiley, 1969.[10] P. Gajer and S. G. Kobourov, GRIP: Graph drawing with intelligent placement. Journal of Graph Algorithms and Applications, 6 (3): 203–224, 2002.[11] S. Grivet, D. Auber, J. Domenger, and G. Melancon, Bubble tree drawing algorithm. In International Conference on Computer Vision and Graphics, pages 633–641, 2004.[12] S. Hachul and M. Jünger, Drawing large graphs with a potential-field-based multilevel algorithm. In Proc. 12th Int. Symp. on Graph Drawing, volume 3383 of LNCS, pages 285–295. Springer-Verlag, 2004.[13] 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. Springer-Verlag, 2005.[14] C. Kimberling, Central points and central lines in the plane of a triangle. Mathematics Magazine, 67 (3): 163–187, 1994.[15] Y. Koren, L. Carmel, and D. Harel, Drawing huge graphs by algebraic multigrid optimization. Multiscale Modeling and Simulation, 1 (4): 645–673, 2003.[16] Y. Koren and D. Harel, Graph drawing by high-dimensional embedding. In Proc. Graph Drawing (GD'02), volume 2528 of LNCS, pages 207–219, 2002.[17] T. Munzner, H3: Laying out large directed graphs in 3D hyperbolic space. In Proc. IEEE Symposium on Information Visualization (InfoVis'97), pages 2–10, 1997.[18] O. Niggemann and B. Stein, A meta heuristic for graph drawing, learning the optimal graph-drawing method for clustered graphs. In AVI 2000: Proc. of the Working Conference on Advanced Visual Interfaces, pages 286–289, 2000.[19] A. Noack, An energy model for visual graph clustering. In Proc. 11th Int. Symp. on Graph Drawing, volume 2912 of LNCS, pages 425–436. Springer-Verlag, 2003.[20] J. M. Six and I. G. Tollis, A framework for circular drawings of networks. In Proc. Graph Drawing (GD'99), volume 1731 of LNCS, pages 107–116. Springer, Berlin, 1999.[21] S. S. Skiena, The Algorithm Design Manual. Springer-Verlag, 1998.[22] S. T. Teoh and K. Ma., RINGS A technique for visualizing large hierarchies. In Proc. Graph Drawing (GD'02), volume 2528 of LNCS, pages 268–275, 2002.[23] C. Walshaw, A multilevel algorithm for force-directed graph drawing. Journal of Graph Algorithms, 7 (3): 253–285, 2003.
Index Terms:
Graph and Network Visualization, Quasi-Tree
Citation:
Daniel Archambault, Tamara Munzner, David Auber, "Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected Components," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 813-820, Sept. 2006, doi:10.1109/TVCG.2006.177
