Three-dimensional graph drawing by Kamada-Kawai method with Barzilai-Borwein method

摘要

This article presents a modification of Kamada-Kawai method (KK) which was designed to produce layouts of simple undirected graphs. Graphs drawn by Kamada-Kawai algorithm exhibit symmetries, tend to produce crossing-free layouts for planar graphs. Original KK uses Newton-Raphson method which needs computation of Hessian matrix in every iteration. It requires higher number of computational operations. This prevents the usage of this method for both large graphs and three-dimensional graphs. Presented idea is to modify KK by Barzilai-Borwein method (BB) which is also iterative method and does not work with Hessian matrix. It enables to use the advantage of the `spring' theory from KK and removes the computational demands of KK. In this article we test presented modification for the drawing of three-dimensional graph.