Abstract We introduce C lusterix , a novel hybrid visualization model for representing hierarchically clustered networks, which also supports directed and weighted edges. C lusterix offers an integrated view of both the network and its full cluster hierarchy by compactly visualizing the cluster inclusion tree enriched with links of the network. This is achieved through matrix‐based representations at various hierarchy levels, combined with a node‐link style linear layout at the leaf level. To support layout computation based on C lusterix , we propose two algorithmic approaches: an exact Integer Linear Program and a fast heuristic, both aimed at minimizing edge crossings. We present an extensive experimental comparison of these algorithmic approaches to highlight the trade‐offs between efficiency and effectiveness. Moreover, as a proof of concept for our model, we developed an interactive visualization system based on C lusterix and evaluated its performance through case studies and qualitative feedback from experts in different application domains.

User interfaces for inspecting spatio-temporal events often allow their users to filter the events by specifying a time window with a time slider. We consider the case that filtered events are visualized on a map using textual or iconic labels. However, to ensure a clear visualization, not all filtered events are annotated with a label. We present algorithms for setting up a data structure that encodes for every possible time window the set of displayed labels. Our algorithms ensure that the displayed labels never overlap and guarantee the stability of the labeling during certain basic interactions with the time slider. Assuming that the labels have different priorities (weights), we aim to maximize the weight of the displayed labels integrated over all possible time windows. As basic interactions, we consider moving the entire time window, symmetrically scaling it, and dragging one of its endpoints. We consider two stability requirements: (1) during a basic interaction, a label should appear and disappear at most once; (2) if a label is displayed for a time window $Q$Q, then it is also displayed for all the time windows contained in $Q$Q and that contain its timestamp. We prove that finding an optimal solution is NP-hard and propose efficient constant-factor approximation algorithms for unit-square and unit-disk labels, as well as a fast greedy heuristic for arbitrarily shaped labels. In experiments on real-world data, we compare the non-exact algorithms with an exact approach through integer linear programming.

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights.

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews.

The visualization of spatio-temporal data helps researchers understand global processes such as animal migration. In particular, interactively restricting the data to different time windows reveals new insights into the short-term and long-term changes of the research data. Inspired by this use case, we consider the visualization of point data annotated with time stamps. We pick up classical, grid-based density maps as the underlying visualization technique and enhance them with an efficient data structure for arbitrarily specified time-window queries. The running time of the queries is logarithmic in the total number of points and linear in the number of actually colored cells. In experiments on real-world data we show that the data structure answers time-window queries within milliseconds, which supports the interactive exploration of large point sets. Further, the data structure can be used to visualize additional decision problems, e.g., it can answer whether the sum or maximum of additional weights given with the points exceed a certain threshold. We have defined the data structure general enough to also support multiple thresholds expressed by different colors.

The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.