High-Quality Ultra-Compact Grid Layout of Grouped Networks

Fig. 1: Grid systems in typographic layout, UI design and an example of our proposed grid layout for a power-graph. With graphic designers playing an increasing role in the design of user interfaces for phone, tablet and desktop operating systems, this traditional grid-based design aesthetic is becoming more popular in these media. A case in point is Microsoft’s “Modern ” interface which seeks to unify app-design across devices. This resurgence of the grid-design aesthetic in new media leads us to re-examine some of the aesthetic assumptions that have been made in designing layout methods for network diagrams. Abstract — Prior research into network layout has focused on fast heuristic techniques for layout of large networks, or complex multi-stage pipelines for higher quality layout of small graphs. Improvements to these pipeline techniques, especially for orthogonal-style layout, are difficult and practical results have been slight in recent years. Yet, as discussed in this paper, there remain significant issues in the quality of the layouts produced by these techniques, even for quite small networks. This is especially true when layout with additional grouping constraints is required. The first contribution of this paper is to investigate an ultra-compact, grid-like network layout aesthetic that is motivated by the grid arrangements that are used almost universally by designers in typographical layout. Since the time when these heuristic and pipeline-based graph-layout methods were conceived, generic technologies (MIP, CP and SAT) for solving combinatorial and mixed-integer optimization problems have improved massively. The second contribution of this paper is to reassess whether these techniques can be used for high-quality layout of small graphs. While they are fast enough for graphs of up to 50 nodes we found these methods do not scale up. Our third contribution is a large-neighborhood search meta-heuristic approach that is scalable to larger networks. Index Terms—Network visualization, graph drawing, power graph, optimization, large-neighborhood search