Graph Drawing by Force-directed Placement

SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 21(1 1), 1129-1164 (NOVEMBER 1991) Graph Drawing by Force-directed Placement THOMAS M. J. FRUCHTERMAN* AND EDWARD M. REINGOLD Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue, Urbana, IL 61801-2987, U.S.A. SUMMARY We present a modification of the spring-embedder model of Eades [ Congresses Numerantium, 42, 149–160, (1984)] for drawing undirected graphs with straight edges. Our heuristic strives for uniform edge lengths, and we develop it in analogy to forces in natural

systems, for a simple, elegant, conceptually- intuitive, and efficient algorithm. KEY WORDS Graph drawing Force-directed placement Multi-level techniques Simulated annealing THE GRAPH-DRAWING PROBLEM A graph G = (V,E) is a set V of vertices and a set E of edges, in which an edge joins a pair of vertices. 1 Normally, graphs are depicted with their vertices as points in a plane and their edges as line or curve segments connecting those points. There are different styles of representation, suited to different types of graphs or different purposes of presentation. We concentrate on the most general class of graphs: undirected graphs, drawn with straight edges. In this paper, we introduce an algor- ithm that attempts to produce aesthetically-pleasing, two-dimensional pictures of graphs by doing simplified simulations of physical systems. We are concerned with drawing undirected graphs according to some generally accepted aesthetic criteria: 2 1. Distribute the vertices evenly in the frame. 2. Minimize edge crossings. 3. Make edge lengths uniform. 4. Reflect inherent symmetry. 5. Conform to the frame. Our algorithm does not explicitly strive for these goals, but does well at distributing vertices evenly, making edge lengths uniform, and reflecting symmetry. Our goals for the implementation are speed and simplicity. PREVIOUS WORK Our algorithm for drawing undirected graphs is based on the work of Eades 3 which, in turn, evolved from a VLSI technique called force-directed placement. 4 We begin by quoting Eades’ explanation of his-‘metaphor’: * Current address: Delfin Systems, 1349 Moffett Park Drive, Sunnyvale, CA 94089, U.S.A. 0038–0644/91/111129–36$18.00 Received 22 June © 1991 by John Wiley & Sons, Ltd. Revised 12 March 1990 1991 1130 T. M. J. FRUCHTERMAN AND E. M. REINGOLD The basic idea is as follows. To embed [lay out] a graph we replace the vertices by steel rings and replace each edge with a spring to form a mechanical system . . . The vertices are placed in some initial layout and let go so that the spring forces on the rings move the system to a minimal energy state. Eades modelled a graph as a physical system of rings and springs, but his implemen- tation did not reflect Hooke’s law;* rather, he chose his own formula for the forces exerted by the springs. Another important deviation from the physical reality is the application of the forces: repulsive forces are calculated between every pair of vertices, but attractive forces are calculated only...

Website: bflite.orcaapp.com | Filesize: -
No of Page(s): 36
Download Graph Drawing by Force-directed Placement.pdf