Non-Euclidean Spring Embedders

Jürgen Pfeffer, 9626384

S. Kobourov and K. Wampler, Non-Euclidean Spring Embedders, IEEE 2004, Austin, Texas, 2004

Motivation

Aims of Graph Drawing:

n Distribute the vertices evenly in the frame

n Minimize edge crossings

n Make edge lengths uniform

n Reflect inherent symmetry

Spring Embedders: Basics

Some of the most flexible algorithms for calculating layouts of simple undirected graphs belong to a class known as forcedirected algorithms. Force-directed algorithms are a well-known and powerful tool for laying out graphs. Also known as spring embedders, such algorithms calculate the layout of a graph using only information contained within the structure of the graph itself. Such methods define an energy function in such a way that low energies correspond to layouts in which adjacent nodes are near some pre-specified distance from each other, but in which non-adjacent nodes are well-spaced. A layout for a graph is then calculated by finding a (often local) minimum of this objective function. [1]

n Graph Drawing by Force-directed Placement

n Repulsive Forces

n Attractive Forces

Standard Algorithm:

n Kamada-Kawai (1989)

n Fruchterman-Reingold (1991)

Non-Euclidean Spring Embedding

Much of the work on non-Euclidean graph drawing has been done in hyperbolic space [11, 13] which offers certain advantages over Euclidean space. For example, in hyperbolic space it is possible to compute a layout for a complete tree with both uniform edge lengths and uniform distribution of nodes. Furthermore, some of the embeddings of hyperbolic space into Euclidean space naturally provide a fish-eye view of the space, which is useful for “focus+context” visualization.

euclidean space hyperbolic space spherical space

Accomplished

The paper in hand shows an common way for layout optimizing in general non-euclidean space. My special interest main concern was with the euclidean spring embedder by Kamada/Kawai [3]. I completed the following production steps:

1. Kamada Kawai

2. Optimized Kamada Kawai (N³ ’ N²)

3. Hyperbolic Kamada Kawai

4. Hyperbolic Projection

Program Environment:

Borland Delphi 7 (Source)

References

[1] S. Kobourov and K. Wampler, Non-Euclidean Spring Embedders, IEEE 2004, Austin, Texas, 2004

[2] P. Eades, A heuristic for graph drawing. Congressus Numerantium, 42:149–160, 1984.

[3] T. Kamada and S. Kawai, An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7–15, Apr. 1989.

[4] T. M. J. Fruchterman and E. M. Reingold, Graph drawing by force-directed placement. Software — Practice and Experience, 21(11):1129–1164, 1991.