Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected Components
|
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
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb