A Parallel Simulated Annealing Algorithm for Generating 3D Layouts of Undirected Graphs

Monien, Burkhard and Ramme, Friedhelm and Salmen, Helmut (1996) A Parallel Simulated Annealing Algorithm for Generating 3D Layouts of Undirected Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 396-408 (Official URL: http://dx.doi.org/10.1007/BFb0021823).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021823
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
M Methods > M.200 Animation
ID Code:183

Repository Staff Only: item control page

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 ist 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

[Parix] 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