Alluvial connectivity in multi-channel networks in rivers and estuaries.

Channels in rivers and estuaries are the main paths of fluvial and tidal currents that transport sediment through the system. While network representations of multi-channel systems and their connectivity are quite useful for characterisation of braiding patterns and dynamics, the recognition of channels and their properties is complicated because of the large bed elevation variations, such as shallow shoals and bed steps that render channels visually disconnected. We present and analyse two mathematically rigorous methods to identify channel networks from a terrain model of the river bed. Both methods construct a dense network of locally steepest-descent channels from saddle points on the terrain, and select a subset of channels with a certain minimum sediment volume between them. This is closely linked to the main mechanism of channel formation and change by displacement of sediment volume. The two methods differ in how they compute these sediment volumes: either globally through the entire length of the river, or locally. We compare the methods for the measured bathymetry of the Western Scheldt estuary, The Netherlands, over the past decades. The global method is overly sensitive to small changes elsewhere in the network compared to the local method. We conclude that the local method works best conceptually and for stability reasons. The associated concept of alluvial connectivity between channels in a network is thus the inverse of the volume of sediment that must be displaced to merge the channels. Our method opens up possibilities for new analyses as shown in two examples. First, it shows a clear pattern of scale dependence on volume of the total network length and of the number of nodes by a power law relation, showing that the smaller channels are relatively much shorter. Second, channel bifurcations were found to be predominantly mildly asymmetrical, which is unexpected from fluvial bifurcation theory.

Simultaneous Matrix Orderings for Graph Collections.

Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph G can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice. Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people. To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously. The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran's I, a spatial auto-correlation metric, which captures the full range of established patterns. Moran's I refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran's I in this context. An ordering that maximizes Moran's I can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP. We evaluated our methods for simultaneous orderings on real-world datasets using Moran's I as the quality metric. Our results show that our collection-aware approach matches or improves performance compared to the union approach, depending on the similarity of the graphs in the collection. Specifically, our Moran's I-based collection-aware leaf order implementation consistently outperforms other implementations. Our collection-aware implementations carry no significant additional computational costs.

A Simple Pipeline for Coherent Grid Maps.

Grid maps are spatial arrangements of simple tiles (often squares or hexagons), each of which represents a spatial element. They are an established, effective way to show complex data per spatial element, using visual encodings within each tile ranging from simple coloring to nested small-multiples visualizations. An effective grid map is coherent with the underlying geographic space: the tiles maintain the contiguity, neighborhoods and identifiability of the corresponding spatial elements, while the grid map as a whole maintains the global shape of the input. Of particular importance are salient local features of the global shape which need to be represented by tiles assigned to the appropriate spatial elements. State-of-the-art techniques can adequately deal only with simple cases, such as close-to-uniform spatial distributions or global shapes that have few characteristic features. We introduce a simple fully-automated 3-step pipeline for computing coherent grid maps. Each step is a well-studied problem: shape decomposition based on salient features, tile-based Mosaic Cartograms, and point-set matching. Our pipeline is a seamless composition of existing techniques for these problems and results in high-quality grid maps. We provide an implementation, demonstrate the efficacy of our approach on various complex datasets, and compare it to the state-of-the-art.

Geometry and Topology of Estuary and Braided River Channel Networks Automatically Extracted From Topographic Data.

Automatic extraction of channel networks from topography in systems with multiple interconnected channels, like braided rivers and estuaries, remains a major challenge in hydrology and geomorphology. Representing channelized systems as networks provides a mathematical framework for analyzing transport and geomorphology. In this paper, we introduce a mathematically rigorous methodology and software for extracting channel network topology and geometry from digital elevation models (DEMs) and analyze such channel networks in estuaries and braided rivers. Channels are represented as network links, while channel confluences and bifurcations are represented as network nodes. We analyze and compare DEMs from the field and those generated by numerical modeling. We use a metric called the volume parameter that characterizes the volume of deposited material separating channels to quantify the volume of reworkable sediment deposited between links, which is a measure for the spatial scale associated with each network link. Scale asymmetry is observed in most links downstream of bifurcations, indicating geometric asymmetry and bifurcation stability. The length of links relative to system size scales with volume parameter value to the power of 0.24-0.35, while the number of links decreases and does not exhibit power law behavior. Link depth distributions indicate that the estuaries studied tend to organize around a deep main channel that exists at the largest scale while braided rivers have channel depths that are more evenly distributed across scales. The methods and results presented establish a benchmark for quantifying the topology and geometry of multichannel networks from DEMs with a new automatic extraction tool.

SolarView: Low Distortion Radial Embedding with a Focus.

We propose a novel type of low distortion radial embedding which focuses on one specific entity and its closest neighbors. Our embedding preserves near-exact distances to the focus entity and aims to minimize distortion between the other entities. We present an interactive exploration tool SolarView which places the focus entity at the center of a "solar system" and embeds its neighbors guided by concentric circles. SolarView provides an implementation of our novel embedding and several state-of-the-art dimensionality reduction and embedding techniques, which we adapted to our setting in various ways. We experimentally evaluated our embedding and compared it to these state-of-the-art techniques. The results show that our embedding competes with these techniques and achieves low distortion in practice. Our method performs particularly well when the visualization, and hence the embedding, adheres to the solar system design principle of our application. Nonetheless-as with all dimensionality reduction techniques-the distortion may be high. We leverage interaction techniques to give clear visual cues that allow users to accurately judge distortion. We illustrate the use of SolarView by exploring the high-dimensional metric space of bibliographic entity similarities.

Stable Treemaps via Local Moves.

Treemaps are a popular tool to visualize hierarchical data: items are represented by nested rectangles and the area of each rectangle corresponds to the data being visualized for this item. The visual quality of a treemap is commonly measured via the aspect ratio of the rectangles. If the data changes, then a second important quality criterion is the stability of the treemap: how much does the treemap change as the data changes. We present a novel stable treemapping algorithm that has very high visual quality. Whereas existing treemapping algorithms generally recompute the treemap every time the input changes, our algorithm changes the layout of the treemap using only local modifications. This approach not only gives us direct control over stability, but it also allows us to use a larger set of possible layouts, thus provably resulting in treemaps of higher visual quality compared to existing algorithms. We further prove that we can reach all possible treemap layouts using only our local modifications. Furthermore, we introduce a new measure for stability that better captures the relative positions of rectangles. We finally show via experiments on real-world data that our algorithm outperforms existing treemapping algorithms also in practice on either visual quality and/or stability. Our algorithm scores high on stability regardless of whether we use an existing stability measure or our new measure.

Multi-Granular Trend Detection for Time-Series Analysis.

Time series (such as stock prices) and ensembles (such as model runs for weather forecasts) are two important types of one-dimensional time-varying data. Such data is readily available in large quantities but visual analysis of the raw data quickly becomes infeasible, even for moderately sized data sets. Trend detection is an effective way to simplify time-varying data and to summarize salient information for visual display and interactive analysis. We propose a geometric model for trend-detection in one-dimensional time-varying data, inspired by topological grouping structures for moving objects in two- or higher-dimensional space. Our model gives provable guarantees on the trends detected and uses three natural parameters: granularity, support-size, and duration. These parameters can be changed on-demand. Our system also supports a variety of selection brushes and a time-sweep to facilitate refined searches and interactive visualization of (sub-)trends. We explore different visual styles and interactions through which trends, their persistence, and evolution can be explored.

Visual Encoding of Dissimilarity Data via Topology-Preserving Map Deformation.

We present an efficient technique for topology-preserving map deformation and apply it to the visualization of dissimilarity data in a geographic context. Map deformation techniques such as value-by-area cartograms are well studied. However, using deformation to highlight (dis)similarity between locations on a map in terms of their underlying data attributes is novel. We also identify an alternative way to represent dissimilarities on a map through the use of visual overlays. These overlays are complementary to deformation techniques and enable us to assess the quality of the deformation as well as to explore the design space of blending the two methods. Finally, we demonstrate how these techniques can be useful in several-quite different-applied contexts: travel-time visualization, social demographics research and understanding energy flowing in a wide-area power-grid.

Exploring Curved Schematization of Territorial Outlines.

Hand-drawn schematized maps traditionally make extensive use of curves. However, there are few automated approaches for curved schematization; most previous work focuses on straight lines. We present a new algorithm for area-preserving curved schematization of territorial outlines. Our algorithm converts a simple polygon into a schematic crossing-free representation using circular arcs. We use two basic operations to iteratively replace consecutive arcs until the desired complexity is reached. Our results are not restricted to arcs ending at input vertices. The method can be steered towards different degrees of "curviness": we can encourage or discourage the use of arcs with a large central angle via a single parameter. Our method creates visually pleasing results even for very low output complexities. To evaluate the effectiveness of our design choices, we present a geometric evaluation of the resulting schematizations. Besides the geometric qualities of our algorithm, we also investigate the potential of curved schematization as a concept. We conducted an online user study investigating the effectiveness of curved schematizations compared to straight-line schematizations. While the visual complexity of curved shapes was judged higher than that of straight-line shapes, users generally preferred curved schematizations. We observed that curves significantly improved the ability of users to match schematized shapes of moderate complexity to their unschematized equivalents.

Analysis and visualisation of movement: an interdisciplinary review.

The processes that cause and influence movement are one of the main points of enquiry in movement ecology. However, ecology is not the only discipline interested in movement: a number of information sciences are specialising in analysis and visualisation of movement data. The recent explosion in availability and complexity of movement data has resulted in a call in ecology for new appropriate methods that would be able to take full advantage of the increasingly complex and growing data volume. One way in which this could be done is to form interdisciplinary collaborations between ecologists and experts from information sciences that analyse movement. In this paper we present an overview of new movement analysis and visualisation methodologies resulting from such an interdisciplinary research network: the European COST Action "MOVE - Knowledge Discovery from Moving Objects" (http://www.move-cost.info). This international network evolved over four years and brought together some 140 researchers from different disciplines: those that collect movement data (out of which the movement ecology was the largest represented group) and those that specialise in developing methods for analysis and visualisation of such data (represented in MOVE by computational geometry, geographic information science, visualisation and visual analytics). We present MOVE achievements and at the same time put them in ecological context by exploring relevant ecological themes to which MOVE studies do or potentially could contribute.

Stenomaps: Shorthand for shapes.

We address some of the challenges in representing spatial data with a novel form of geometric abstraction-the stenomap. The stenomap comprises a series of smoothly curving linear glyphs that each represent both the boundary and the area of a polygon. We present an efficient algorithm to automatically generate these open, C1-continuous splines from a set of input polygons. Feature points of the input polygons are detected using the medial axis to maintain important shape properties. We use dynamic programming to compute a planar non-intersecting spline representing each polygon's base shape. The results are stylised glyphs whose appearance may be parameterised and that offer new possibilities in the 'cartographic design space'. We compare our glyphs with existing forms of geometric schematisation and discuss their relative merits and shortcomings. We describe several use cases including the depiction of uncertain model data in the form of hurricane track forecasting; minimal ink thematic mapping; and the depiction of continuous statistical data.

KelpFusion: a hybrid set visualization technique.

We present KelpFusion: a method for depicting set membership of items on a map or other visualization using continuous boundaries. KelpFusion is a hybrid representation that bridges hull techniques such as Bubble Sets and Euler diagrams and line- and graph-based techniques such as LineSets and Kelp Diagrams. We describe an algorithm based on shortest-path graphs to compute KelpFusion visualizations. Based on a single parameter, the shortest-path graph varies from the minimal spanning tree to the convex hull of a point set. Shortest-path graphs aim to capture the shape of a point set and smoothly adapt to sets of varying densities. KelpFusion fills enclosed faces based on a set of simple legibility rules. We present the results of a controlled experiment comparing KelpFusion to Bubble Sets and LineSets. We conclude that KelpFusion outperforms Bubble Sets both in accuracy and completion time and outperforms LineSets in completion time.

Analysis and visualization of animal movement.

The interdisciplinary workshop 'Analysis and Visualization of Moving Objects' was held at the Lorentz Centre in Leiden, The Netherlands, from 27 June to 1 July 2011. It brought together international specialists from ecology, computer science and geographical information science actively involved in the exploration, visualization and analysis of moving objects, such as marine reptiles, mammals, birds, storms, ships, cars and pedestrians. The aim was to share expertise, methodologies, data and common questions between different fields, and to work towards making significant advances in movement research. A data challenge based on GPS tracking of lesser black-backed gulls (Larus fuscus) was used to stimulate initial discussions, cross-fertilization between research groups and to serve as an initial focus for activities during the workshop.

Flow map layout via spiral trees.

Flow maps are thematic maps that visualize the movement of objects, such as people or goods, between geographic regions. One or more sources are connected to several targets by lines whose thickness corresponds to the amount of flow between a source and a target. Good flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding self-intersections. Most flow maps are still drawn by hand and only few automated methods exist. Some of the known algorithms do not support edge-bundling and those that do, cannot guarantee crossing-free flows. We present a new algorithmic method that uses edge-bundling and computes crossing-free flows of high visual quality. Our method is based on so-called spiral trees, a novel type of Steiner tree which uses logarithmic spirals. Spiral trees naturally induce a clustering on the targets and smoothly bundle lines. Our flows can also avoid obstacles, such as map features, region outlines, or even the targets. We demonstrate our approach with extensive experiments.

Necklace maps.

Statistical data associated with geographic regions is nowadays globally available in large amounts and hence automated methods to visually display these data are in high demand. There are several well-established thematic map types for quantitative data on the ratio-scale associated with regions: choropleth maps, cartograms, and proportional symbol maps. However, all these maps suffer from limitations, especially if large data values are associated with small regions. To overcome these limitations, we propose a novel type of quantitative thematic map, the necklace map. In a necklace map, the regions of the underlying two-dimensional map are projected onto intervals on a one-dimensional curve (the necklace) that surrounds the map regions. Symbols are scaled such that their area corresponds to the data of their region and placed without overlap inside the corresponding interval on the necklace. Necklace maps appear clear and uncluttered and allow for comparatively large symbol sizes. They visualize data sets well which are not proportional to region sizes. The linear ordering of the symbols along the necklace facilitates an easy comparison of symbol sizes. One map can contain several nested or disjoint necklaces to visualize clustered data. The advantages of necklace maps come at a price: the association between a symbol and its region is weaker than with other types of maps. Interactivity can help to strengthen this association if necessary. We present an automated approach to generate necklace maps which allows the user to interactively control the final symbol placement. We validate our approach with experiments using various data sets and maps.