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

@Article{Bartolomeo2022StratisfimalLayoutModular,
  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         = {2022},
  issn         = {1941-0506},
  note         = {VIS '21. Preprint \& Supplemental Material: https://osf.io/qdyt9},
  pages        = {1-1},
  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},
  journaltitle = {IEEE Transactions on Visualization and Computer Graphics},
  series       = {VIS/TVCG},
}