Graph drawing by force‐directed placement

Software - Practice and Experience - Tập 21 Số 11 - Trang 1129-1164 - 1991
Thomas M. J. Fruchterman1, Edward M. Reingold1
1Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue, Urbana, IL 61801–2987, U.S.A.

Tóm tắt

AbstractWe present a modification of the spring‐embedder model of Eades [Congressus Numerantium, 42, 149–160, (1984)] for drawing undirected graphs with straight edges. Our heuristic strives for uniform edge lengths, and we develop it in analogy to forces in natural systems, for a simple, elegant, conceptually‐intuitive, and efficient algorithm.

Từ khóa


Tài liệu tham khảo

10.21236/AD0705364

Eades P., Algorithms for drawing graphs: an annotated bibliography, Networks

Eades P., 1984, A heuristic for graph drawing, Congressus Numerantium, 42, 149

10.1109/TCS.1979.1084652

Tipler P. A., 1982, Physics

Bentley J., 1986, Programming Pearls

10.7551/mitpress/5750.001.0001

Kamada T., 1988, Technical Report 88–007

10.1016/0020-0190(89)90102-6

R.DavidsonandD.Harel ‘Drawing graphs nicely using simulated annealing’ Technical Report CS89–13 Department of Applied Mathematics and Computer Science. The Weizmann Institute Rehovot Israel July 1989. A revised version dated April 1991 has been submitted toCommunications of the ACM.

10.1126/science.220.4598.671

10.1007/978-1-4613-1627-5

Hearn D., 1986, Computer Graphics

10.1137/0906008

L. K.Grover ‘Standard cell placement using simulated sintering’ Proceedings 24th Design Automation Conference 1987 pp.56–59.

Breuer M. A., 1977, Min‐cut placement, Journal of Design Automation and Fault Tolerant Computing, 1, 343

Kernighan B. W., 1989, The AWK Programming Language

Stoustrup B., 1986, The C++ Programming Language

Dewhurst S. C., 1989, Programming in C++

10.1016/0734-189X(88)90116-8

Reingold E. M., 1977, Combinatorial Algorithms: Theory and Practice.