IEEE Transactions on Visualization and Computer Graphics

Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization

Y. Wang, Y. Wang, Y. Sun, L. Zhu, K. Lu, C. Fu, M. Sedlmair, O. Deussen, B. Chen

Material

Abstract

We present an improved stress majorization method that incorporates various constraints, including directional constraints without the necessity of solving a constraint optimization problem. This is achieved by reformulating the stress function to impose constraints on both the edge vectors and lengths instead of just on the edge lengths (node distances). This is a unified framework for both constrained and unconstrained graph visualizations, where we can model most existing layout constraints, as well as develop new ones such as the star shapes and cluster separation constraints within stress majorization. This improvement also allows us to parallelize computation with an efficient GPU conjugant gradient solver, which yields fast and stable solutions, even for large graphs. As a result, we allow the constraint-based exploration of large graphs with 10K nodes – an approach which previous methods cannot support.

BibTeX

@article{Wang2018RevisitingStressMajorization,
  author    = {Y. Wang, Y. Wang, Y. Sun, L. Zhu, K. Lu, C. Fu, M. Sedlmair, O. Deussen, B. Chen},
  doi       = {10.1109/TVCG.2017.2745919},
  issn      = {1077-2626},
  journal   = {IEEE Transactions on Visualization and Computer Graphics},
  keywords  = {computational geometry;data visualisation;gradient methods;graph theory;graphics processing units;interactive systems;mathematics computing;optimisation;parallel processing;improved stress majorization method;directional constraints;layout constraints;GPU conjugant gradient solver;interactive constrained graph visualization;cluster separation constraints;unconstrained graph visualizations;constrained graph visualizations;node distances;edge lengths;edge vectors;constraint optimization problem;Stress;Layout;Visualization;Springs;Optimization;Computational modeling;Shape;Graph visualization;stress majorization;constraints},
  month     = {jan},
  number    = {1},
  pages     = {489--499},
  title     = {Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization},
  url       = {http://graphics.uni-konstanz.de/publikationen/Wang2018RevisitingStressMajorization},
  volume    = {24},
  year      = {2018}
}