STRATISFIMAL LAYOUT: A modular optimization model for laying out layered node-link network visualizations

@Article{DiBartolomeo2021StratisfimalLayoutModular,
  author   = {Di~Bartolomeo, Sara and Riedewald, Mirek and Gatterbauer, Wolfgang and Dunne, Cody},
  journal  = {IEEE Transactions on Visualization and Computer Graphics},
  title    = {{STRATISFIMAL LAYOUT}: A modular optimization model for laying out layered node-link network visualizations},
  year     = {2021},
  issn     = {1941-0506},
  note     = {VIS '21. Preprint \& supplemental material: \url{https://osf.io/qdyt9}},
  number   = {1},
  pages    = {324--334},
  volume   = {28},
  abstract = {Node-link visualizations are a familiar and powerful tool for displaying the relationships in a network. The readability of these visualizations highly depends on the spatial layout used for the nodes. In this paper, we focus on computing layered layouts, in which nodes are aligned on a set of parallel axes to better expose hierarchical or sequential relationships. Heuristic-based layouts are widely used as they scale well to larger networks and usually create readable, albeit sub-optimal, visualizations. We instead use a layout optimization model that prioritizes optimality – as compared to scalability – because an optimal solution not only represents the best attainable result, but can also serve as a baseline to evaluate the effectiveness of layout heuristics. We take an important step towards powerful and flexible network visualization by proposing STRATISFIMAL LAYOUT, a modular integer-linear-programming formulation that can consider several important readability criteria simultaneously – crossing reduction, edge bendiness, and nested and multi-layer groups. The layout can be adapted to diverse use cases through its modularity. Individual features can be enabled and customized depending on the application. We provide open-source and documented implementations of the layout, both for web-based and desktop visualizations. As a proof-of-concept, we apply it to the problem of visualizing complicated SQL queries, which have features that we believe cannot be addressed by existing layout optimization models. We also include a benchmark network generator and the results of an empirical evaluation to assess the performance trade-offs of our design choices. A full version of this paper with all appendices, data, and source code is available at https://osf.io/qdyt9 with live examples at https://visdunneright.github.io/stratisfimal/.},
  doi      = {10.1109/TVCG.2021.3114756},
  series   = {VIS/TVCG},
}