A Fast Adaptive Layout Algorithm for Undirected Graphs (Extended Abstract and System Demonstration)

Frick, Arne and Ludwig, Andreas and Mehldau, Heiko (1995) A Fast Adaptive Layout Algorithm for Undirected Graphs (Extended Abstract and System Demonstration). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 388-403 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_393).

Full text not available from this repository.


We present a randomized adaptive layout algorithm for nicely drawing undirected graphs that is based on the spring-embedding paradigm and contains several new heuristics to improve the convergence, including local temperatures, gravitational forces and the detection of rotations and oscillations. The proposed algorithm achieves drawings of high quality on a wide range of graphs with standard settings. Moreover, the algorithm is fast, being thus applicable on general undirected graphs of substantially larger size and complexity than before [9,6,3]. Aesthetically pleasing solutions are found in most cases. We give empirical data for the running time of the algorithm and the quality of the computed layouts.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_393
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.400 Force-directed / Energy-based
ID Code:239

Repository Staff Only: item control page


G. Di Battista, P. Eades, H. de Freysseix, P. Rosenstiehl, and R. Tamassia, editors. Proceedings of the ALCOM International Workshop on Graph DRawing 1993. ALCOM, 1993.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Report, Brown University, June 1994.

R. Davidson and David Harel. Drawing graphs nicely using simulated annealing. Technical Report CS89-13, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 1989. revised July 1993, to appear in Communications of the ACM.

P. Eades. A heuristic for graph drawing. Congressus Numernatium, 42:149-160, 1984.

C. J. Fisk, D. L. Caskey, and L. E. West. ACCEL: Automated circuit card ething layout. Proceedings of the IEEE, 55(11):1971-1982, November 1967.

T.M.J. Fruchterman and E.M. Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, 21, 1991.

M. Himsolt. Graphed: A graphical platform for the implementation of graph algorithms In Proceedings of Graph Drawing '94, LNCS, Princeton, New Jersey, October 10-12 1994. DIMACS Workshop on Graph Drawing, Springer. this volume.

N. R. Quinn Jr. and M. A. Breuer. A forced directed component placement procedure for printed circuit boards. IEEE Transactions on Circuits and Systems, CAS-26(6):377-388, 1979.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs, Information Processing Letters, 31, 1989.

Scott Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Optimization by simulated annealing. Science, 220: 671-680, 1983.

Donald E. Knuth. Seminumerical Algorithms, volume 2. Addison-Wesley, 2nd edition, 1981.

J.B. Manning. Geometric symmetry in graphs. PhD thesis, Purdue University, December 1990.

N. Metropolis, W. Rosenbluth, and A.H. Teller. Equation of state calculations by fast computer machines. J. Chem. Phys., 21:1087, 1953.

D. Tunkelang. A layout algorithm for undirected graphs. In Graph Drawing '93, ALCOM International Workshop PARIS 1993 on Graph Drawing and Topological Graph Algorithms, September 1993.

H. Watanabe. Heuristic graph displayer for G-Base. International Journal of Man-Machine Studies, 30:287-302, 1989.