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

Illustration of the modular components that can be combined into a STRATISFIMAL LAYOUT algorithm.
Our goal is to make complicated networks easier to read. We achieve this by formulating readability criteria as a constrained optimization problem. Our optimization model for laying out layered node-link visualizations includes several modular, customizable components. Each addresses a different readability criteria or network feature — hence the building blocks metaphor. This modularity allows the layout to be tailored for diverse use cases. Here we illustrate some of the features of our Integer Linear Programming (ILP) formulation, which we call STRATISFIMAL LAYOUT—combining the words stratified (arranged in layers) and optimal.
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/.
Materials
PDF | Preprint | DOI | Homepage | Supplement | Code | Video Preview | Video Presentation | BibTeX
Authors
Citation

Khoury Vis Lab — Northeastern University
* West Village H, Room 302, 440 Huntington Ave, Boston, MA 02115, USA
* 100 Fore Street, Portland, ME 04101, USA
* Carnegie Hall, 201, 5000 MacArthur Blvd, Oakland, CA 94613, USA