Visualization of clustered directed acyclic graphs with node interleaving

ABSTRACT

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). E-Spring algorithm, extended from the popular spring embedder model, eliminates node overlaps in clustered DAGs by modeling nodes as charged particles whose repulsion is controlled by edges modeled as springs. The drawing process needs to reach a stable state when the average distances of separation between nodes are near optimal. This paper presents an enhancement to E-Spring to introduce a stopping condition, which reduces equilibrium distances between nodes and therefore results in a significantly reduced area for DAG visualization. It imposes an upper bound on the repulsive forces between nodes based on graph geometry. The algorithm employs node interleaving to eliminate any residual node overlaps. These new techniques have been validated by visualizing eBay buyer-seller relationships and resulted in overall area reductions in the range of 45% to 79%.

REFERENCES

• 1: Helen C. Purchase , Robert F. Cohen , Murray James, Validating Graph Drawing Aesthetics, Proceedings of the Symposium on Graph Drawing, p.435-446, September 20-22, 1995
• 2: Michael Kaufmann , Dorothea Wagner, Drawing graphs: methods and models, Springer-Verlag, London, 2001
• 3: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 4: Wanchun Li , Peter Eades , Nikola Nikolov, Using spring algorithms to remove node overlapping, proceedings of the 2005 Asia-Pacific symposium on Information visualisation, p.131-140, January 01, 2005, Sydney, Australia
• 5: Aaron Quigley , Peter Eades, FADE: Graph Drawing, Clustering, and Visual Abstraction, Proceedings of the 8th International Symposium on Graph Drawing, p.197-210, September 20-23, 2000
• 6: Xiaodi Huang , Wei Lai , A. S. M. Sajeev , Junbin Gao, A new algorithm for removing node overlapping in graph visualization, Information Sciences: an International Journal, v.177 n.14, p.2821-2844, July, 2007 [doi>10.1016/j.ins.2007.02.016]
• 7: Peter Eades , Xuemin Lin, Spring Algorithms and Symmetry, Proceedings of the Third Annual International Conference on Computing and Combinatorics, p.202-211, August 20-22, 1997
• 8: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• 9: Pushpa Kumar , Kang Zhang , Yuke Wang, Visualization of Clustered Directed Acyclic Graphs without Node Overlapping, Proceedings of the 2008 12th International Conference Information Visualisation, p.38-43, July 09-11, 2008 [doi>10.1109/IV.2008.85]
• 10: Leymann F. Web Services Flow Language (WSFL 1.0), IBM, May 2001.
• 11: Kevin Korb , Ann E. Nicholson, Bayesian Artificial Intelligence, CRC Press, Inc., Boca Raton, FL, 2003
• 12: Eades P. A heuristic for graph drawing. Congressus Numerantium, 42 (1984), 149--160.
• 13: Martyn Taylor , Peter Rodgers, Applying Graphical Design Techniques to Graph Visualisation, Proceedings of the Ninth International Conference on Information Visualisation, p.651-656, July 06-08, 2005 [doi>10.1109/IV.2005.19]
• 14: Hugo A. D. do Nascimento , Peter Eades, User Hints for map labeling, Journal of Visual Languages and Computing, v.19 n.1, p.39-74, February, 2008 [doi>10.1016/j.jvlc.2006.03.004]
• 15: Pushpa Kumar , Kang Zhang, Social Network Analysis of Online Marketplaces, Proceedings of the IEEE International Conference on e-Business Engineering, p.363-367, October 24-26, 2007 [doi>10.1109/ICEBE.2007.130]
• 16: Wei Lai, Layout Adjustment and Boundary Detection for a Diagram, Computer Graphics International 2001, p.351-354, July 03-06, 2001
• 17: Yeh, C., and Gu, Y. Y. Technique to minimise area overhead for delay driven clustering. IEE Proceedings of Computers and Digital Techniques, 142, 6 (November 1995), 401--406.
• 18: Ivan Herman , M. Scott Marshall , Guy Melançon, Density Functions for Visual Attributes and Effective Partitioning in Graph Visualization, Proceedings of the IEEE Symposium on Information Vizualization 2000, p.49, October 09-10, 2000
• 19: Lux, M., Klieber, W., and Granitzer, M. Caliph & Emir: Semantics in Multimedia Retrieval and Annotation. In Proceedings for the 19th International CODATA Conference The Information Society: New Horizons For Science (Berlin, Germany, 7--10 November 2004). International Council for Science: Committee on Data for Science and Technology, 2004, 3--7.
• 20: A. Efrat , S. Kobourov , M. Stepp , C. Wenk, Growing fat graphs, Proceedings of the eighteenth annual symposium on Computational geometry, p.277-278, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513434]
• 21: Wanchun Li , Peter Eades , Seok-Hee Hong, Navigating Software Architectures with Constant Visual Complexity, Proceedings of the 2005 IEEE Symposium on Visual Languages and Human-Centric Computing, p.225-232, September 20-24, 2005 [doi>10.1109/VLHCC.2005.52]
• 22: G. W. Furnas, Generalized fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems, p.16-23, April 13-17, 1986, Boston, Massachusetts, United States
• 23: Peter Eades , Qing-Wen Feng, Multilevel Visualization of Clustered Graphs, Proceedings of the Symposium on Graph Drawing, p.101-112, September 18-20, 1996
• 24: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119]
• 25: Eades, P., Lai, W., Misue, K., and Sugiyama, K. Layout adjustment and the mental map. Journal of Visual Languages & Computing, 6 (1995), 83--210.
• 26: URL: http://www.graphdrawing.org
• 27: URL: http://www.prefuse.org

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

General Terms:
Algorithms

Keywords:
directed acyclic graphs, graph drawing, node interleaving, overlapping nodes, visualization