di Bartolomeo Sara, Riedewald Mirek, Gatterbauer Wolfgang, Dunne Cody
IEEE Trans Vis Comput Graph. 2022 Jan;28(1):324-334. doi: 10.1109/TVCG.2021.3114756. Epub 2021 Dec 24.
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 osf.io/qdyt9 with live examples at https://visdunneright.github.io/stratisfimal/.
节点链接可视化是一种用于展示网络中关系的常见且强大的工具。这些可视化的可读性在很大程度上取决于节点所使用的空间布局。在本文中，我们专注于计算分层布局，其中节点在一组平行轴上对齐，以更好地展现层次或顺序关系。基于启发式的布局被广泛使用，因为它们能很好地扩展到更大的网络，并且通常能创建出可读的（尽管不是最优的）可视化效果。相反，我们使用一种布局优化模型，该模型优先考虑最优性（与可扩展性相比），因为最优解不仅代表了可达到的最佳结果，还可以作为评估布局启发式方法有效性的基线。通过提出Stratisfimal布局，我们朝着强大且灵活的网络可视化迈出了重要一步，Stratisfimal布局是一种模块化整数线性规划公式，它可以同时考虑几个重要的可读性标准——减少交叉、边的弯曲度以及嵌套和多层组。该布局可以通过其模块化适应各种不同的用例。可以根据应用启用和定制各个功能。我们提供了该布局的开源且有文档记录的实现，适用于基于网络和桌面的可视化。作为概念验证，我们将其应用于可视化复杂SQL查询的问题，这些查询具有我们认为现有布局优化模型无法解决的特征。我们还包括一个基准网络生成器以及实证评估的结果，以评估我们设计选择的性能权衡。本文的完整版本以及所有附录、数据和源代码可在osf.io/qdyt9获取，实时示例可在https://visdunneright.github.io/stratisfimal/查看。
