Sparse stress minimization

Sparse Stress Layout

Method

The sparse stress layout is a heuristic to approximate the (full) stress layout. The goal of the stress minimization is to find a layout, $x$, such that $\sum _{i<j}w_{ij}(||x_{i}-x_{j}||-d_{ij})^{2}{\text{ is as small as possible.}}$ In other words stress minimization tries to find a layout in which the euclidean distance of each pair of nodes matches their graph-theoretical distance, i.e. shortest-path distance.

In comparison to the (full) stress minimization, sparse stress on the one hand requires less space and running time, but on the other hand the resulting layouts have a slightly lower quality. The space and running time reduction is achieved by restricting the stress function from $n^{2}$ to $m+np$ with $p$ denoting the number of pivots.

More detailed background information can be found in

• Mark Ortmann, Mirza Klimenta, and Ulrik Brandes: A sparse Stress Model, GD'16, 18-32, 2016.