Logo

Login

Improved Force-Directed Layouts

Gansner, Emden R. and North, Stephen (1998) Improved Force-Directed Layouts. [Conference Paper]

Full text not available from this repository.

Abstract

Techniques for drawing graphs based on force-directed placement and virtual physical models have proven surprisingly successful in producing good layouts of undirected graphs. Aspects of symmetry, structure, clustering and reasonable vertex distribution arise from initial, formless clouds of points. However, when nodes must be labeled and point vertices are replaced by non-point vertices, simple force-directed models produce unreadable drawings, even for a moderate number of nodes. This paper describes the application of two post-processing techniques that can be applied to any initial vertex layout to produce uncluttered layouts with non-point nodes.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.630 Labeling
M Methods > M.400 Force-directed / Energy-based
ID Code:405
Deposited By:Arnopolina, Galina
Deposited On:17 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=364

Repository Staff Only: item control page

References

1. J. Abello and E. Gansner. Short and smooth polygonal paths. In C. Lucchesi and A. Moura, editors, LATIN '98: Theoretical Informatics, vol. 1380 of LNCS, pages 151-162, 1998.

2. F.J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 76-87. Springer-Verlag, 1996.

3. J. Cohen. Drawing graphs to convey proximity: an incremental arrangement method. ACM Transactions on Computer-Human Interaction, 4(11):197-229, 1987.

4. Ron Davidson and David Harel. Drawing graphs nicely using simmulated annealing. ACM Transactions on Graphics, 15(4):301-331, 1996.

5. D. Dobkin, E. Gansner, E. Koutsofios, and S. North. Implementing a generalpurpose edge router. In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 262-271. Springer Verlag, 1998.

6. P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

7. P. Eades and X. Lin. Spring algorithms and symmetry. Computing and Combinatorics, LNCS 1276:202-211.

8. U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. Brandenburg, editor, Symposium on Graph Drawing 95, vol. 1027 of LNCS. Springer-Verlag, 1996, pp. 254-266.

9. A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs. In Proceedings of DIMACS International Workshop on GD '94, LNCS 894, Princeton, New Jersey, USA, October 1994. Springer-Verlag.

10. T.M.J. Fruchtermann and E.M. Reingold. Graph drawing by force-directed placement. Software Practice and Experience, 21(11):1129-1164, November 1991.

11. E.R. Gansner, E. Koutsofios, S.C. North, and K. P. Vo. A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19:214-230, 1993.

12. E.R. Gansner, S.C. North, and K. P. Vo. DAG - A program that draws directed graphs. Softw. - Pract. Exp., 18(11):1047-1062, 1988.

13. W. He and K. Mariott. Constrained graph layout. In S. North, editor, Symposium on Graph Drawing 96, vol. 1190 of LNCS. Springer-Verlag, 1997, pp. 217-232.

14. T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, April 1989.

15. T. Kamps, J. Kleinz, and J. Read. Constraint-based spring-model algorithm for graph layout. In Symp. on Graph Drawing, GD '95, LNCS 1027, pages 349-360, Passau, Germany, September 1995. Springer-Verlag.

16. E. Koutsofios and S.C. North. Intertool connections. In B. Krishnamurty, editor, Practical Reusable UNIX Software, chapter 11, pages 300-315. John Wiley & Sons, New York, 1995.

17. J. Kruskal and J. Seery. Designing network diagrams. In Proc. First General Conf. on Social Graphics, pages 22-50, 1980.

18. X. Lin. Analysis of Algorithms for Drawing Graphs. PhD. thesis, Dept. of Comp. Sci. University Queensland, Australia, 1992.

19. R.J. Lipton, S.C. North, and J.S. Sandberg. A method for drawing graphs. In 'proc. 1st Annu ACM Sympos. Comput. Geom., pages 153-160, 1985.

20. K. Lyons. Cluster busting in anchored graph drawing. In Proc. of the 1992 CAS Conference, pages 7-16, 1992.

21. K. Lyons, H. Meijer, and D. Rappaport. Algorithms for cluster busting in anchored graph drawing. Journal of Graph Algorithms and Applications, 2(1):1-24, 1998.

22. J. O'Rourke. Computational Geometry in C. Cambridge University Press, Cambridge, 1994.

23. M.-A. Storey and H. Muller. Graph layout adjustment strategies. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 487-499, Springer-Verlag, 1996.

24. K. Sugiyama and K. Misue. A simple and unified method for drawing graphs: magnetic-spring algorithm. In Proceedings of DIMACS International Workshop on GD '94, LNCS 894, Princeton, New Jersey, USA, October 1994. Springer-Verlag.

25. K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man. Cybern., SMC-11(2):109-125, 1981.

26. R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.

27. R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, SMC-18(1):61-79, 1988.

28. X. wang and I. Miyamoto. Generating customized layouts. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 504-515. Springer-Verlag, 1996.

29. G. Wills. Nicheworks - interactive visualization of very large graphs. In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 403-414. Springer Verlag, 1998.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.