KamadaKawai

Kamada-Kawai is a force-directed graph drawing algorithm developed by Teiko Kamada and William Kawai in 1989. It is designed to place the vertices of an undirected graph so that their Euclidean distances reflect the graph-theoretic distances between vertices, typically the lengths of shortest paths.

The method begins by computing the shortest-path distance between every pair of vertices, often using Floyd-Warshall or Dijkstra’s algorithm. These distances determine the ideal geometric distance l_ij between each pair of vertices i and j. In weighted graphs, the edge weights influence these distances. An energy function is then defined as E = 1/2 sum over all pairs i<j of w_ij (||p_i − p_j|| − l_ij)^2, where p_i denotes the position of vertex i and w_ij are weights, commonly chosen as proportional to 1/l_ij^2. The layout is obtained by minimizing E, typically with a Newton-Raphson iterative procedure that moves the vertex positions to reduce energy, focusing on the displacements with the largest contribution to E.

Kamada-Kawai is particularly suitable for small to medium-sized graphs because the required all-pairs distance computation and iterative optimization can be computationally intensive (often O(n^3) for typical implementations). It tends to produce layouts that preserve global structure and reveal clusters and path geometry effectively.

Variants and limitations include adaptations for weighted or directed graphs and refinements to improve scalability. While highly regarded in graph drawing, it is commonly used in conjunction with or contrasted against other spring-embedding methods and majorization-based approaches for larger networks.