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 2D 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.

Example SPRING_EMBEDDING()

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

Example 3D_SPRING_EMBEDDING()

Tip

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