Graph Drawing by Stress Majorization.pdfVIP

Graph Drawing by Stress Majorization Emden R. Gansner, Yehuda Koren and Stephen North ATT Labs — Research Florham Park, NJ 07932 {erg,yehuda,north}@ Abstract. One of the most popular graph drawing methods is based on achiev- ing graph-theoretic target distances. This method was used by Kamada and Kawai [15], who formulated it as an energy optimization problem. Their energy is known in the multidimensional scaling (MDS) community as the stress function . In this work, we show how to draw graphs by stress majorization, adapting a technique known in the MDS community for more than two decades. It appears that ma- jorization has advantages over the technique of Kamada and Kawai in running time and stability. We also found the majorization-based optimization being es- sential to a few extensions to the basic energy model. These extensions can im- prove layout quality and computation speed in practice. 1 Introduction A graph is a structure G(V ={1, . . . , n}, E) representing a binary relation E over a set of nodes V . Visualizing graphs is a challenging problem, requiring algorithms that faithfully represent the graph’s structure and the relative similarities of the nodes [4, 16]. Here we will focus on drawing undirected graphs with straight-line edges. The most popular approach defines, sometimes implicitly, an energy, or cost func- tion, based on some virtual physical model of the graph. Minimizing this function de- termines an optimal drawing. In the approach considered here, originally proposed by Kamada and Kawai[15], a nice drawing relates to good isometry. We have an ideal dis- tance dij given for every pair of nodes i and j , modeled as a spring. Given a 2-D layout, where node i is placed at point X , the energy of the