Drawing graphs nicely using simulated annealing

ACM Transactions on Graphics - Tập 15 Số 4 - Trang 301-331 - 1996
Ron Davidson1, David Harel1
1Weizmann Institute of Science, Rehovot, Israel

Tóm tắt

The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely.” Our algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result. The algorithm is flexible, in that the relative weights of the criteria can be changed. For graphs of modest size it produces good results, competitive with those produced by other methods, notably, the “spring method” and its variants.

Từ khóa


Tài liệu tham khảo

BERGE C. 1973. Graphs and Hypergraphs. North-Holland Amsterdam.]] BERGE C. 1973. Graphs and Hypergraphs. North-Holland Amsterdam.]]

BERNARD , M. A. 1981 . On the automated drawing of graphs . In Proceedings of the 3rd Caribbean Conference on Combinatorics and Computing, 43-55 .]] BERNARD, M. A. 1981. On the automated drawing of graphs. In Proceedings of the 3rd Caribbean Conference on Combinatorics and Computing, 43-55.]]

DE BOOR , C. 1978. A Practical Guide to Splines . Springer-Verlag , New York .]] DE BOOR, C. 1978. A Practical Guide to Splines. Springer-Verlag, New York.]]

10.1016/0164-1212(84)90006-2

10.1016/0925-7721(94)00014-X

EADES , P. 1984 . A heuristic for graph drawing . Cong. Numer. 42 , 149 - 160 .]] EADES, P. 1984. A heuristic for graph drawing. Cong. Numer. 42, 149-160.]]

10.1002/spe.4380211102

10.1002/spe.4380181104

10.1137/0604033

10.1109/CDC.1985.268599

10.1145/42411.42414

10.1109/32.54292

10.1006/jvlc.1995.1014

HAREL D. AND SARDAS M. 1996. An incremental drawing algorithm for planar graphs. Algorithmica to appear.]] HAREL D. AND SARDAS M. 1996. An incremental drawing algorithm for planar graphs. Algorithmica to appear.]]

10.1109/32.60298

10.5555/85867.85882

10.1287/opre.39.3.378

10.1002/jgt.3190110306

KAMADA , T. 1989. Visualizing Abstract Objects and Relations. World Scientific , Teaneck, N.J., (See also On visualization of abstract objects and relations. D. Sc. Thesis , The University of Tokyo , Dec. 1988 .)]] KAMADA, T. 1989. Visualizing Abstract Objects and Relations. World Scientific, Teaneck, N.J., (See also On visualization of abstract objects and relations. D. Sc. Thesis, The University of Tokyo, Dec. 1988.)]]

10.1016/0020-0190(89)90102-6

10.1126/science.220.4598.671

VAN LAARHOVEN , P. J. M. AND tARTS , E. H. L. 1987 . Simulated Annealing : Theory and Applications, D. Reidel, Dordrecht .]] VAN LAARHOVEN, P. J. M. AND tARTS, E. H. L. 1987. Simulated Annealing: Theory and Applications, D. Reidel, Dordrecht.]]

10.1145/323233.323254

10.1080/00207169008803875

MANNING , g. AND ATA LLAH , M.g. 1988 . Fast detection and display of symmetry in trees . Cong. Numer. 64 , 159 - 169 .]] MANNING, g. AND ATALLAH, M.g. 1988. Fast detection and display of symmetry in trees. Cong. Numer. 64, 159-169.]]

10.1063/1.1699114

10.1109/TCAD.1987.1270265

10.1109/21.87055

10.1112/plms/s3-13.1.743

Thông tin
Thông tin xuất bản

ACM Transactions on Graphics

Tập 15 Số 4

301-331

Thông tin tác giả