Abstract
In this paper, we introduce a parallel simulated annealing algorithm for generating aesthetically pleasing straight-line drawings. The proposed algorithm calculates high quality 3D layouts of arbitrary undirected graphs. Due to the 3D layouts, structure information is presented to the human viewer at a glance. The computing time of the algorithm is reduced by a new parallel method for exploiting promising intermediate configurations. As the algorithm avoids running into a local minimum of the cost function, it is applicable for the animation of graphs of reasonably larger size than it was possible before.
Subsequent to the discussion of the algorithm, empirical data for the performance of the algorithm and the quality of the generated layouts are presented.
This work was partially supported by the ESPRIT Basic Research Action No. 7141 (ALCOM II)
Chapter PDF
References
G.D. Battista, P. Eades, R. Tamassia, I.G. Tollis: Algorithms for drawing graphs: An annotated bibliography, Report, Brown University, June 1994
R.F. Cohen, P. Eades, T. Lin, F. Ruskey: Three-Dimensional Graph Drawing, Proc. of Graph Drawing '94, LNCS Springer, Vol. 894, pp. 1–11
R. Davidson, D, Harel: Drawing graphs nicely using simulated annealing, Technical Report CS89-13, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Israel 1989, revised July 1993, to appear in Communications of the ACM
R. Diekmann, R. Lüling, J. Simon: Problem Independent Distributed Simulated Annealing and its Applications, in: R.V.V. Vidal (ed.): Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems, Springer 1993, No. 396, pp. 17–44.
P. Eades: A heuristic for graph drawing, Congressus Numerantium, 1984, Vol. 42, pp. 149–160
P.W. Fowler, T. Pisanski, J. Shawe-Taylor: Molecular Graph Eigenvectors for Molecular Coordinates, Proc. of Graph Drawing '94, LNCS Springer, Vol. 894, pp. 282–285
A. Frick, A. Ludwig, H. Mehldau: A Fast Adaptive Layout Algorithm for Undirected Graphs, Proc. of Graph Drawing '94, LNCS Springer, Vol. 894, pp. 388–403
T.M.J. Fruchtermann, E.M. Reingold: Graph drawing by force-directed placement, Software-Practice and Experience, 1991, Vol. 21, No. 11, pp. 1129–1164
D. Harel, M. Sardas: Randomized Graph Drawing with Heavy-Duty Preprocessing, Technical Report CS93-16, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Israel Oct. 1993
M.D. Huang, F. Romeo, A. Sangiovanni-Vincentelli: An Efficient General Cooling Schedule for Simulated Annealing, IEEE Int. Conf. on Computer Aided Design 1986, pp. 381–384
D.S. Johnson, C.R. Aragon, L. A. McGeoch, C. Schevon: Optimization by Simulated Annealing: An Experimental Evaluation, Part I, ”Graph Partitioning”, Operations Research Vol.37, No.6, pp.865–892, 1989; Optimization by Simulated Annealing: An Experimental Evaluation, Part II, ”Graph Coloring and Number Partitioning”, Operations Research Vol.39, No. 3, pp. 378–406, 1991
T. Kamada, S. Kawai: An algorithm for drawing general undirected graphs, Information Processing Letters, North-Holland 1989, Vol. 31, pp. 7–15
C. Kosak, J. Marks, S. Shieber: Automating the Layout of Network Diagrams with Specified Visual Organization, IEEE Trans. on Systems, Man, and Cybernetics, Vol. 24, No. 3, pp. 440–454
O.E. Otten, L. van Ginneken: The Annealing Algorithm, Kluwer Academic Publishers 1989
Parsytec Computer Ltd.: Parix 1.3: Software Documentation, Aachen
H. Salmen: Dreidimensionale Auslegung beliebiger Graphen mittels parallelem Simulated Annealing Methoden, Master Thesis, Univ. of Paderborn, 1995
D. Tunkelang: A layout algorithm for undirected graphs, In Graph Drawing '93, ALCOM Int. Workshop, Paris 1993
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Monien, B., Ramme, F., Salmen, H. (1996). A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs. In: Brandenburg, F.J. (eds) Graph Drawing. GD 1995. Lecture Notes in Computer Science, vol 1027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0021823
Download citation
DOI: https://doi.org/10.1007/BFb0021823
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60723-6
Online ISBN: 978-3-540-49351-8
eBook Packages: Springer Book Archive