Skip to main content
SpringerLink
Log in

From Tree to Graph - Experiments with E-Spring Algorithm

  • Conference paper
  • First Online:
Visual Information Communication

Abstract

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. E-Spring Algorithm, derived from the popular spring embedder model, was proposed to eliminate node overlaps in the drawings of clustered directed acyclic graphs Gc. In this paper, we apply the E-Spring algorithm to general graphs by minimizing edge-node intersections. Initially, a tree structure is extracted from the original graph using the breadth-first search (BFS) algorithm. The extracted tree is then visualized without node overlaps using the E-Spring algorithm, and the remaining non-tree edges are appended to this visualization. A post-processing step that implements edge routing is performed on the obtained visualization to eliminate residual edge-node intersections. This method has been validated by visualizing eBay buyer-seller relationships and Graph Catalog benchmarking data.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Battista, G.D., Eades, P.: Algorithms for drawing graphs: an annotated bibliography. Computational Geometry. 4, 235–282 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  2. Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, New Jersey, USA (1999)

    MATH  Google Scholar 

  3. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press and McGraw-Hill, New York, USA (2001)

    MATH  Google Scholar 

  4. Cruz, I.F., Twarog, J.P.: 3D Graph Drawing with Simulated Annealing. In: Proceedings of the Symposium on Graph Drawing, pp. 162–165. Springer-Verlag, London, UK (1995)

    Google Scholar 

  5. Davidson, R., Harel, D.: Drawing Graphs Nicely Using Simulated Annealing, ACM Transactions on Graphics. 15, 301–331 (1996)

    Article  Google Scholar 

  6. Dijksta, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik. 1, 269–271 (1959)

    Article  MathSciNet  Google Scholar 

  7. Dolulil, J., Katreniakova, J.: Edge Routing with Fixed Node Positions. In: Proceedings of the 12th International Conference Information Visualisation, pp. 626–631. IEEE Computer Society Washington, DC, USA (2008)

    Chapter  Google Scholar 

  8. Dwyer, T., Marriott, K., Wybrow, M.: Integrating edge routing into force-directed layout. In: Proceedings 14th Intl. Symp. Graph Drawing (GD ’06), pp. 8–19. Springer-Verlag, Berlin, Heidelberg (2007)

    Google Scholar 

  9. Eades, P.: A heuristic for graph drawing. Congressus Numerantium. 42, 149–160 (1984)

    MathSciNet  Google Scholar 

  10. Eades, P., Huang, M.L.: Navigating Clustered Graphs using Force-Directed Methods, Journal of Graph Algorithms and Applications. 4, 157–181 (2000)

    MATH  Google Scholar 

  11. Eades, P., Lai, W., Misue, K., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages and Computing. 6, 83–210 (1995)

    Google Scholar 

  12. Forster, M.: Crossings in Clustered Level Graphs, Ph.D.Dissertation (2004)

    Google Scholar 

  13. Healy, P., Nikolov, N.S.: Graph Drawing. Springer-Verlag, Berlin, Heidelberg (2006)

    Book  MATH  Google Scholar 

  14. Huang, X., Lai, W., Sajeev, A.S.M., Gao, J.: A new algorithm for removing node overlapping in graph visualization. Information Sciences. 177, 2821–2844 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  15. Kakoulis, K.G., Tollis, I.G.: A unified approach to labeling graphical features. In: Proceedings 14th Annual ACM Symposium of Computational Geometry (SoCG’98), pp. 347–356. ACM New York, NY, USA (1998)

    Google Scholar 

  16. Kaufmann, M., Dorothea, W.: Drawing graphs, methods and models. Springer-Verlag, Berlin, Heidelberg (2001)

    Book  MATH  Google Scholar 

  17. Korb, K.B., Nicholson, A.E.: Bayesian Artificial Intelligence. Chapman & Hall, London, UK (2004)

    MATH  Google Scholar 

  18. Kruskal, J.B.: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. American Mathematical Society. 7, 48–50 (1956)

    Article  MathSciNet  Google Scholar 

  19. Kumar, P., Zhang, K.: Social Network Analysis of Online Marketplaces. In: Proceedings IEEE International Conference on e-Business Engineering, pp. 363–367. IEEE Computer Society Washington, DC, USA (2007)

    Google Scholar 

  20. Kumar, P., Zhang, K., Wang, Y.: Visualization of Clustered Directed Acyclic Graphs without Node Overlapping. In: Proceedings 12th International Conference on Information Visualization, pp. 38–43. IEEE Computer Society Washington, DC, USA (2008)

    Chapter  Google Scholar 

  21. Kumar, P., Zhang K.: Visualization of Clustered Directed Acyclic Graphs with Node Interleaving. In: Proceedings of the 24th Annual ACM Symposium on Applied Computing (SAC ‘09), pp. 1800–1805. ACM New York, NY, USA (2009)

    Chapter  Google Scholar 

  22. Kumar, P., Zhang, K.: Node Overlap Removal in Clustered Directed Acyclic Graphs. Journal of Visual Languages and Computing (JVLC). Article in press, doi:10.1016/j.jvlc.2009.04.007 (2009)

    Google Scholar 

  23. Lai, W.: Layout Adjustment and Boundary Detection for a Diagram. In: Proceedings of Computer Graphics International (CGI ’01), pp. 351–354. IEEE Computer Society Washington, DC, USA (2001)

    Chapter  Google Scholar 

  24. Lai, W., Eades, P.: Removing edge-node intersections in drawings of graphs. Information Processing Letters. 81, 105–110 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  25. Larson, R.C., Li, V.O.K.: Finding minimum rectilinear distance paths in the paths in the presence of barriers. Networks. 11, 285–304 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  26. Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks. 14, 393–410 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  27. Leiserson, C.E.: Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing. IEEE Transactions on Computers. 34, 892–901 (1985)

    Google Scholar 

  28. Leymann, F.: Web Services Flow Language (WSFL 1.0), IBM (2001)

    Google Scholar 

  29. Li, W., Eades, P., Nikolov, N.: Using spring algorithms to remove node overlapping. In: Proceedings of the 2005 Asia-Pacific symposium on Information visualization (APVIS ’05), pp. 131–140. Australian Computer Society, Inc. Darlinghurst, Australia (2005)

    Google Scholar 

  30. Lozano-Perez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Communications of ACM. 22, 22560–22570 (1979)

    Article  Google Scholar 

  31. Marriott, K., Stuckey, P., Vam, T., He, W.: Removing Node Overlapping in Graph Layout Using Constrained Optimization. Constraints. 8, 143–171 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  32. Nascimento, H.A.D., Eades, P.: User Hints for map labeling. Journal of Visual Languages and Computing. 19, 39–74 (2008)

    Article  Google Scholar 

  33. Papakostas, A., Tollis, I.G.: Interactive Orthogonal Graph Drawing. IEEE Transactions on Computers. 47, 1297–1309 (1998)

    Article  MathSciNet  Google Scholar 

  34. Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal. 36, 1389–1401 (1957)

    Google Scholar 

  35. Purchase, H.C., Cohen, R.F., James, M.: Validating Graph Drawing Aesthetics. In: Proceedings of the Symposium on Graph Drawing (GD ’95), pp. 435–446. Springer-Verlag, London, UK (1995)

    Google Scholar 

  36. Quigley A., Eades, P.: Graph Drawing, Clustering, and Visual Abstraction. In: Proceedings of the 8th International Symposium on Graph Drawing (GD ’00), pp. 197–210. Springer-Verlag, Berlin, Heidelberg (2000)

    Google Scholar 

  37. Taylor, M., Rodgers, P.: Applying Graphical Design Techniques to Graph Visualization. In: Proceedings of the Ninth International Conference on Information Visualization (IV ’05), pp. 651–656. IEEE Computer Society Washington, DC, USA (2005)

    Chapter  Google Scholar 

  38. ConceptDraw, http://www.conceptdraw.com/en/products/cd5/main.php

  39. Home of Graphdrawing, http://www.graphdrawing.org

  40. Graphviz - Graph Visualization Software, http://www.graphviz.org

  41. Microsoft Office Online – Visio, http://office.microsoft.com/en-us/visio/default.aspx

  42. yWorks, http://www.yworks.com/products/yfiles/doc/developers-guide/index.html

Download references

Author information

Authors and Affiliations

  1. University of Texas at Dallas, 2601 N. Floyd Road, 75063, Richardson, TX, USA

    Pushpa Kumar & Kang Zhang

  2. University of Technology, Broadway, PO Box 123, 2007, Sydney, NSW, Australia

    Mao Lin Huang

Authors
  1. Pushpa Kumar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mao Lin Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pushpa Kumar .

Editor information

Editors and Affiliations

  1. Dept. Information & Technology, University of Technology, Sydney, Broadway, 2007, Australia

    Mao Lin Huang

  2. School of Computing & Mathematics, University of Western Sydney, South Penrith DC, 1797, Australia

    Quang Vinh Nguyen

  3. Dept. Computer Science, University of Texas, Dallas, West Campbell Road 800, Richardson, 75080, U.S.A.

    Kang Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag US

About this paper

Cite this paper

Kumar, P., Zhang, K., Huang, M.L. (2009). From Tree to Graph - Experiments with E-Spring Algorithm. In: Huang, M., Nguyen, Q., Zhang, K. (eds) Visual Information Communication. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-0312-9_3

Download citation

  • DOI: https://doi.org/10.1007/978-1-4419-0312-9_3

  • Published:

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4419-0311-2

  • Online ISBN: 978-1-4419-0312-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation