Related Approaches next up previous
Next: Layout in Layers Up: Force and Energy Controlled Previous: Applications in Compiler Construction

Related Approaches

Genetic layout algorithms [Ma92, Pa89] are very similar to simulated annealing. They are randomized methods that calculate generations of layouts of the same graph. The best layout (according to some quality function similar to the energy function of simulated annealing) is selected as new layout. Generations of layouts are produced by two operations in correspondence to biology: mutations (a layout changes randomly) and crossovers (two layouts are combined into a new layout). After a sequence of mutations and crossovers, the quality function is applied to all layouts. Bad layouts are deleted, and only the best layouts survive. Just as simulated annealing, genetic layout algorithms are relatively slow and need a lot of memory space.

Tunkelang [Tu94] developed a method similar to simulated annealing which does not place the nodes randomly but according to a fixed pattern. The energy function is applied during the initialization in order to find a good initial layout, and afterwards to improve the layout. The disadvantage of this method: with a fixed pattern of node movements some layouts are never taken into account. Thus, the algorithm does not always give optimal results. On the other hand, a good selection of the movement pattern may speed up the heuristics very much.

Spring embedders and simulated annealing do not necessarily produce planar layouts for planar graphs. Harel and Sardas [HaSa93] use a combined approach: First a planar layout (or for nonplanar graphs: a layout with only few edge crossings) is calculated, and afterwards, simulated annealing is used to improve the layout. In this optimization step, all node moves are rejected that would produce edge crossings. This guarantees symmetric, uniform planar layouts for planar graphs.


Georg Sander
Thu Aug 1 15:27:34 PDT 1996