The spring embedders of Eades [Ea84] and Misue und Sugiyama [SuMi94, SuMi95] apply a fixed number of iterations to get the layout. It may happen that the number of iterations is too small, which gives an unbalanced layout, or the number is too high, which is waste of time. Different extensions were proposed to get better termination conditions for the heuristic. Some spring embedders [QuBr79, KaKa89] are based on the energetic states of the nodes. The aim is to minimize the global energy E (the sum of all energetic states). A minimum of E can be found by solving the equation system
for the positions 
of all n nodes.
The equation system can be solved by numerical methods (e.g. the
method of Newton-Raphson [BoPr91]).
However, this only finds some local minimum
of E which is not the global one.
Thus, Davidson and Harel [DaHa89] applied a randomized
optimization method from statistical mechanics: simulated annealing.
In addition to the global energy E, there is a global temperature T
which is lowered as the iterations progress.
In each step, a random move is tried at some node.
If the global energy E gets smaller with the new position of the
node, the move is done.
If E is enlarged by 
, the move is accepted with the probability
otherwise the move is rejected.
The uphill changes of the energy prevent the layout to go
towards a local minimum very early.
By lowering the temperature T in each step, uphill changes get more
improbable as the algorithm progresses.
As long as the temperature is decreased slowly enough,
this randomized method results in uniform and symmetric layouts.
The method has the advantage that no vector calculations are needed,
because no force vectors need to be calculated.
Any complex scalar formula for the energy is allowed, e.g. taking
into account the border of the layout 
and 
, or the number of crossings and overlappings.
Typical formulas are
where
The disadvantage of simulated annealing is the fact that the cooling must be very slow to enforce regularities of the layout. It needs about 10 times more iterations than normal spring embedders (see also [BHR96] for a comparison between spring embedders and simulated annealing). Thus, it is not very well suited for large graphs.
Experiments have shown that the combination of both spring embedding
and simulated annealing can be useful.
We move the nodes in direction of the forces, but add a small random
force
and with a certain probability,
we reject moves that would increase the global energy.
Because the positioning of the nodes is not completely random,
simulated annealing becomes faster, and because the energy state is
checked, it is possible to enforce aesthetics that are not
expressible as force vector.
Fig. 10 shows an example: The spring embedder produces a
symmetric layout of the torus, while the combined method allows
to press the torus into a rectangular border.
