Kamada-Kawai Model

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:

$$stress(X) = \underset{i < j}{\sum} \;w_{ij}(\vert\vert X_{i} - X_{j}\vert\vert - d_{ij})^{2}$$ (2.1)

for some pair of nodes $i$ and $j$ , where $d_{ij}$ is the ideal distance between vertices corresponding to the shortest path between those vertices, $X$ is the set of 2D or 3D coordinates, and $w_{ij} = d_{ij}^{-\alpha}$ Kamada and Kawai choose $\alpha = 2$ , where as Cohen in [4] chose $\alpha = 0$ or $1$ . Choosing $\alpha = 2$ seems to produce the best layout as evidenced in [3,23]. Kamada and Kawai use the Newton-Raphson[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 Kamada-Kawai method preserved the total balance of a graph, and produces layouts with small amounts of edge crossings.