Evolutionary Layout of Graph Transformation Sequences

The evolutionary layout algorithm of graph transformation sequences is based on the well-known spring embedder layout algorithm which fulfills two importent requirements for layouting a graph sequence: the highest single layout quality and the lowest difference between two successive layouts. But this layout algorithm does not fit well for incomplete graph sequences, since we following two new requirements are not fulfilled:

1. the option for future extensions of graph sequences without ruining the layout,
2. by taking also typing of graph edges into account.

So we extended the spring embedder layout algorithm by two new concepts:

1. A concept of node aging and protection of senior node positions in the layout that allows the user to keep track of changes during transformation steps. The persistence of node positions throughout a sequence is most helpful to preserve the mental map. Especially the concept of aging was the reason to name the algorithm an evolutionary layout algorithm.
2. A concept of layout patterns based on edge typing.

All in all, this new layout algorithm tries to solve the following problems for an evolving graph transformation sequence:

1. The quality of every single layout should be as optimal as possible.
2. The mental distance from one layout to its successor layout should be small.
3. The graph sequence may have future extensions, without loosing the layout`s quality.
4. The changes between two graphs should be easily recognizable in the layout of two subsequent graphs.