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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J. Abello and E. Gansner. Short and smooth polygonal paths. In C. Lucchesi and A. Moura, editors, LATIN’98: Theoretical Informatics, volume 1380 of Lecture Notes in Computer Science, pages 151–162, 1998.
F.J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In F.J. Brandenburg, editor, Symposium on Graph Drawing GD’95, volume 1027 of Lecture Notes in Computer Science, pages 76–87, 1996.
J. Cohen. Drawing graphs to convey proximity: an incremental arrangement method. ACM Transactions on Computer-Human Interaction, 4(11):197–229, 1987.
R. Davidson and D. Harel. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 15(4):301–331, 1996.
D. Dobkin, E. Gansner, E. Koutsofios, and S. North. Implementing a general-purpose edge router. In G. DiBattista, editor, Symposium on Graph Drawing GD’97, volume 1353 of Lecture Notes in Computer Science, pages 262–271, 1997.
P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149–160, 1984.
P. Eades and X. Lin. Spring algorithms and symmetry. In COCOON’97, volume 1276 of Lecture Notes in Computer Science, pages 202–211, 1997.
U. Fossmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F.J. Brandenburg, editor, Symposium on Graph Drawing GD’95, volume 1027 of Lecture Notes in Computer Science, pages 254–266, 1996.
A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs. In R. Tamassia and I.G. Tollis, editors, Symposium on Graph Drawing GD’94, volume 894 of Lecture Notes in Computer Science, pages 388–403, 1995.
T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, 21(11):1129–1164, 1991. also as Technical Report UIUCDCS-R-90-1609, Dept. of Computer Science,Univ. of Illinois at Urbana-Champaign, 1990.
E.R. Gansner, E. Koutsofios, S.C. North, and K.P. Vo. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, March 1993.
E.R. Gansner, S.C. North, and K.P. Vo. Dag-a program that draws directed graphs. Software-Practice and Experience, 18(11):1047–1062, 1988.
W. He and K. Marriott. Constrained graph layout. In S.C. North, editor, Symposium on Graph Drawing GD’96, volume 1190 of Lecture Notes in Computer Science, pages 217–232, 1997.
T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31:7–15, 1989.
T. Kamps, J. Kleinz, and J. Read. Constraint-based spring-model algorithm for graph layout. In F.J. Brandenburg, editor, Symposium on Graph Drawing GD’95, volume 1027 of Lecture Notes in Computer Science, pages 349–360, 1996.
E. Koutsofios and S. North. Intertool connections. In B. Krishnamurthy, editor, Practical Reusable UNIX Software, chapter 11, pages 300–315. John Wiley & Sons, New York, 1995.
J. Kruskal and J. Seery. Designing network diagrams. In Proc. First General Conf. on Social Graphics, pages 22–50, 1980.
X. Lin. Analysis of Algorithms for Drawing Graphs. PhD thesis, Department of Computer Science, University of Queensland, 1992.
R. Lipton, S. North, and J. Sandberg. A method for drawing graphs. In Proc. ACM Symp. on Computational Geometry, pages 153–160, 1985.
K. Lyons. Cluster busting in anchored graph drawing. In Proceedings of the 1992 CAS Conference, pages 7–16, 1992.
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.
O’Rourke. Computational Geometry in C. Cambridge University Press, Cambridge, 1994.
M.-A. Storey and H. Muller. Graph layout adjustment strategies. In F.J. Brandenburg, editor, Symposium on Graph Drawing GD’95, volume 1027 of Lecture Notes in Computer Science, pages 487–99, 1996.
K. Sugiyama and K. Misue. A simple and unified method for drawing graphs: Magnetic-spring algorithm. In R. Tamassia and I.G. Tollis, editors, Symposium on Graph Drawing GD’94, volume 894 of Lecture Notes in Computer Science, pages 364–375, 1995.
K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Transactions on Systems, Man and Cybernetics, SMC-11(2):109–125, 1981.
R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Computing, 16(3):421–444, 1987.
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.
X. Wang and I. Miyamoto. Generating customized layouts. In F.J. Brandenburg, editor, Symposium on Graph Drawing GD’95, volume 1027 of Lecture Notes in Computer Science, pages 504–515, 1996.
G. Wills. Nicheworks-interactive visualization of very large graphs. In G. Di-Battista, editor, Symposium on Graph Drawing GD’97, volume 1353 of Lecture Notes in Computer Science, pages 403–414, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gansner, E.R., North, S.C. (1998). Improved Force-Directed Layouts. In: Whitesides, S.H. (eds) Graph Drawing. GD 1998. Lecture Notes in Computer Science, vol 1547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-37623-2_28
Download citation
DOI: https://doi.org/10.1007/3-540-37623-2_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65473-5
Online ISBN: 978-3-540-37623-1
eBook Packages: Springer Book Archive