Drawing graphs nicely using simulated annealing

ABSTRACT

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.

REFERENCES

• 1: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 2: BERNARD, M. A. 1981. On the automated drawing of graphs. In Proceedings of the 3rd Caribbean Conference on Combinatorics and Computing, 43-55.
• 3: DE BOOR, C. 1978. A Practical Guide to Splines. Springer-Verlag, New York.
• 4: C Batini , M Talamo , R Tamassia, Computer aided layout of entity relationship diagrams, Journal of Systems and Software, v.4 n.2-3, p.163-173, July 1984 [doi>10.1016/0164-1212(84)90006-2]
• 5: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, v.4 n.5, p.235-282, Oct. 1994 [doi>10.1016/0925-7721(94)00014-X]
• 6: EADES, P. 1984. A heuristic for graph drawing. Cong. Numer. 42, 149-160.
• 7: Thomas M. J. Fruchterman , Edward M. Reingold, Graph drawing by force-directed placement, Software—Practice & Experience, v.21 n.11, p.1129-1164, Nov. 1991 [doi>10.1002/spe.4380211102]
• 8: E. R. Gansner , S. C. North , K. P. Vo, DAG—a program that draws directed graphs, Software—Practice & Experience, v.18 n.11, p.1047-1062, Nov. 1988 [doi>10.1002/spe.4380181104]
• 9: GAREY, M. R. AND JOHNSON, D. S. 1983. Crossing number is NP-complete. SIAM J. Alg. Discrete Meth. 4, 312-316.
• 10: HAJEK, B. 1985. A tutorial survey of theory and applications of simulated annealing. In Proceedings of the 24th Conference on Decision and Control, 755-760.
• 11: David Harel, On visual formalisms, Communications of the ACM, v.31 n.5, p.514-530, May 1988 [doi>10.1145/42411.42414]
• 12: David Harel , Amir Pnueli , Hagi Lachover , Amnon Naamad , Michal Politi , Rivi Sherman , Aharon Shtull-Trauring , Mark Trakhtenbrot, STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, v.16 n.4, p.403-414, April 1990 [doi>10.1109/32.54292]
• 13: HAREL, D. AND SARDAS, M. 1995. Randomized graph drawing with heavy-duty preprocessing. J. Visual Lang. Comput. 6, 233-253.
• 14: HAREL, D. AND SARDAS, M. 1996. An incremental drawing algorithm for planar graphs. Algorithmica, to appear.
• 15: Allan Heydon , Mark W. Maimone , J. D. Tygar , Jeannette M. Wing , Amy Moormann Zaremski, Miro: Visual Specification of Security, IEEE Transactions on Software Engineering, v.16 n.10, p.1185-1197, October 1990 [doi>10.1109/32.60298]
• 16: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989 [doi>10.1287/opre.37.6.865]
• 17: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations Research, v.39 n.3, p.378-406, May-June 1991 [doi>10.1287/opre.39.3.378]
• 18: JOHNSON, D. S. AND POLLACK, H. O. 1987. Hypergraph planarity and the complexity of drawing Venn diagrams. J. Graph Theory 11, 309-325.
• 19: 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.)
• 20: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• 21: KIRKPATRICK, S., GELATT JR., C. D., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 671-680.
• 22: P. J. M. Laarhoven , E. H. L. Aarts, Simulated annealing: theory and applications, Kluwer Academic Publishers, Norwell, MA, 1987
• 23: R. J. Lipton , S. C. North , J. S. Sandberg, A method for drawing graphs, Proceedings of the first annual symposium on Computational geometry, p.153-160, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323254]
• 24: MAKINEN, E. 1990. How to draw a hypergraph. Int. J. Comput. Math. 34, 177-185.
• 25: MANNING, g. AND ATALLAH, M.g. 1988. Fast detection and display of symmetry in trees. Cong. Numer. 64, 159-169.
• 26: METROPOLIS, N., ROSENBLUTH, A., ROSENBLUTH, M., TELLER, A., AND TELLER, E. 1953. Equa-tion of state calculations by fast computing machines. J. Chem. Phys. 21, 1087-1091.
• 27: SIARRY, P., BERGONZI, L., AND DREYFUS, G. 1987. Thermodynamic optimization of block placement. IEEE Trans. Comput. Aided Des. 6, 211-221.
• 28: Roberto Tamassia , Giuseppe Di Battista , Carlo Batini, Automatic graph drawing and readability of diagrams, IEEE Transactions on Systems, Man and Cybernetics, v.18 n.1, p.61-79, January/February 1988 [doi>10.1109/21.87055]
• 29: TUTTE, W. T. 1963. How to draw a graph. In Proceedings of the London Mathematical Society 13, 743-768.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  D. Software
  D.0 GENERAL

  E. Data
  E.0 GENERAL

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
aesthetics, graph drawing, simulated annealing