Abstract Given a set of rectangles embedded in the plane, we consider the problem of adjusting the layout to remove all overlap while preserving the orthogonal order of the rectangles. The objective is to minimize the displacement of the rectangles. We call this problem Minimum-Displacement Overlap Removal (mdor). Our interest in this problem is motivated by the application of displaying metadata of archaeological sites. Because most existing overlap removal algorithms are not designed to minimize displacement while preserving orthogonal order, we present and compare several approaches which are tailored to our particular usecase. We introduce a new overlap removal heuristic which we call reArrange. Although conceptually simple, it is very effective in removing the overlap while keeping the displacement small. Furthermore, we propose an additional procedure to repair the orthogonal order after every iteration, with which we extend both our new heuristic and PRISM, a widely used overlap removal algorithm. We compare the performance of both approaches with and without this order repair method. The experimental results indicate that reArrange is very effective for heterogeneous input data where the overlap is concentrated in few dense regions.

We present a novel uncertain network visualization technique based on node-link diagrams. Nodes expand spatially in our probabilistic graph layout, depending on the underlying probability distributions of edges. The visualization is created by computing a two-dimensional graph embedding that combines samples from the probabilistic graph. A Monte Carlo process is used to decompose a probabilistic graph into its possible instances and to continue with our graph layout technique. Splatting and edge bundling are used to visualize point clouds and network topology. The results provide insights into probability distributions for the entire network-not only for individual nodes and edges. We validate our approach using three data sets that represent a wide range of network types: synthetic data, protein-protein interactions from the STRING database, and travel times extracted from Google Maps. Our approach reveals general limitations of the force-directed layout and allows the user to recognize that some nodes of the graph are at a specific position just by chance.

Small-world networks have characteristically low pairwise shortest-path distances, causing distance-based layout methods to generate hairball drawings. Recent approaches thus aim at finding a sparser representation of the graph to amplify variations in pairwise distances. Since the effect of sparsification on the layout is difficult to describe analytically, the incorporated filtering parameters of these approaches typically have to be selected manually and individually for each input instance. We here propose the use of graph invariants to determine suitable parameters automatically. This allows us to perform adaptive filtering to obtain drawings in which the cluster structure is most prominent. The approach is based on an empirical relationship between input and output characteristics that is derived from real and synthetic networks.Experimental evaluation shows the effectiveness of our approach and suggests that it can be used by default to increase the robustness of force-directed layout methods.

Abstract Voronoi treemaps represent hierarchies as nested polygons. We here show that, contrary to the apparent popular belief, utilization of an algorithm for weighted Voronoi diagrams is not only feasible, but also more efficient than previous low‐resolution approximations, even when the latter are implemented on graphics hardware. More precisely, we propose an instantiation of Lloyd's method for centroidal Voronoi diagrams with Aurenhammer's algorithm for power diagrams that yields an algorithm running in 𝒪(n log n) rather than Ω(n2) time per iteration, with n the number of sites. We describe its implementation and present evidence that it is faster also in practice.

We propose a method to highlight query hits in hierarchically clustered collections of interrelated items such as digital libraries or knowledge bases. The method is based on the idea that organizing search results similarly to their arrangement on a fixed reference map facilitates orientation and assessment by preserving a user's mental map. Here, the reference map is built from an MDS layout of the items in a Voronoi treemap representing their hierarchical clustering, and we use techniques from dynamic graph layout to align query results with the map. The approach is illustrated on an archive of newspaper articles.