- Graph Drawing by Stress Majorization
- Emden Gansner, Yehuda Koren, and Stephen North
- Graph Drawing pp. 239-250, 2004.
PDF (1083K)
- Abstract
One of the most popular graph drawing methods is based on achieving
graph-theoretic target distances. This method was used by Kamada and Kawai,
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 majorization
has advantages over the technique of Kamada and Kawai in running
time and stability. We also found the majorization-based optimization being essential
to a few extensions to the basic energy model. These extensions can improve
layout quality and computation speed in practice.
|
