Graphs are becoming popular as a means of visualizing order, accessibility, or distance information. This paper is concerned with efficient methods of conveying vertex proximity, that is, of arranging the vertices so their pairwise screen distances match their target distances. Cohen discusses an adequate measure of the quality of a representation and then presents the method.
To evaluate his and other methods, the author defines a family Sk of stress functions of a given representation as an accumulation of the difference between vertex spatial configuration and the target distances. S0 stress measures absolute errors in long and short distances, S2 penalizes errors in proportion to the target distance, and S1 is a “semiproportional” measure. These functions are shown to be similar to others presented elsewhere.
Now the problem can be restated as a numerical problem consisting of the minimization of Sk. This approach has been tried elsewhere and, like many other combinatorial problems, shows little stability or convergence to local minima. (Simulated annealing might be useful here.) The author then proposes an incremental approach to arranging vertices. Given a small portion that can be considered a good starting point, the author develops an algorithm based on the heuristic that chooses close vertices to remain together. He shows that this algorithm is fast and copes with clustering adequately, at least for the examples provided. Minimizing absolute stress converges quickly, but may fail to reach the global minimum. Proportional stress, in contrast, is robust but converges slowly. Thus, semiproportional stress is a good compromise solution.
