Next: Stress Majorisation
Up: Further work on the
Previous: Further work on the
In their paper, Kamada and Kawai [25] put forward that in some scenarios, the reduction of the number of edge crossings that a graph possesses is not a good aesthetic criterion for a layout algorithm to implement. They state that the total balance of the layout which is related to the individual characteristics of the graph is just as important, or can be considered more important than the reduction of edge crossings in the graph given a particular scenario. Kamada and Kawai calculates the total balance of the graph, as the square summation of the differences between the ideal distance and the actual distance for all vertices by calculating:

(2.1) 
for some pair of nodes
and
, where
is the ideal distance between vertices corresponding to the shortest path between those vertices,
is the set of 2D or 3D coordinates, and
Kamada and Kawai choose
, where as Cohen in [4] chose
or
. Choosing
seems to produce the best layout as evidenced in [3,23]. Kamada and Kawai use the NewtonRaphson[10] method to optimise with respect to a single vertex. By iteratively solving for each vertex the overall stress is reduced.
By approximating and minimising the stress in Eq , the KamadaKawai method preserved the total balance of a graph, and produces layouts with small amounts of edge crossings.
Next: Stress Majorisation
Up: Further work on the
Previous: Further work on the
20061107