Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Graph Drawing Algorithms > Spring Embedding

Spring Embedding

Graphs can be used to represent relational information. This is the reason why it is often useful to draw graphs in order to visualize this relational information.

Spring Embedder are force directed layout algorithms. All edges are drawn as straight lines.

Force directed layout algorithms model the input graph as a system of forces and try to find a minimum energy configuration of this system.

The idea of spring embedders is to simulate the graph as a system of mass particles. The nodes are the mass particles and the edges are springs between the particles. The algorithms try to minimize the energy of this physical system.

Example of 2D Spring Embedding
Example 2D Spring Embedding

Example of 3D Spring Embedding
Example 3D Spring Embedding

LEDA Functions for Spring Embedders

SPRING_EMBEDDING(): Let G=(V,E) be a graph. SPRING_EMBEDDING() computes a spring embedding of G in the plane. In the resulting drawing edges may cross even if the graph is planar. It is also possible that edges cross nodes.


D3_SPRING_EMBEDDING(): Let G=(V,E) be a graph. D3_EMBEDDING() computes a spring embedding of G in 3D.



The best results of spring embedding are obtained for sparse, tree-like graphs.

See also:

Graph Drawing Algorithms

Algorithms for Planar Graphs

Planar Maps

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms


Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH