Visualizing and Interacting with Geospatial Networks: A Survey and Design Space

3.1 Terminology for data types

Networks are considered synonymous to graphs in this survey. A graph is formally defined as a pair , where is a set of nodes (or vertices) and is a set of links (or edges), with each link either being a set of two nodes (undirected graphs) or an ordered set of two nodes (directed graphs). Both nodes and links can have an arbitrary set of attributes and associated with them.

In a spatial network, nodes are associated with inherent and semantically meaningful spatial positions. For example, in brain connectivity networks, nodes are distinct regions, and their position information is essential for understanding brain activities. Networks with arbitrarily determined positions such as those generated by network layout algorithms are not considered spatial networks. Fixed node positions increase the difficulties when designing visualizations for spatial network data.

Geospatial networks are a subgroup of spatial networks where the node locations are of a geographic nature, that is these nodes represent locations on the Earth or other planets. As locations on the surface of approximately (but not exactly) spherical bodies, geospatial locations have characteristics that differentiate them from other spatial data, making the distinction between spatial and geospatial essential. Besides precise geographic coordinates, locations can be defined more semantically and come with their own set of challenges. For example, areas can be well-defined and non-overlapping (e.g. Germany, France), roughly defined with fuzzy boundaries (Sahara desert), nested (Scotland, UK), and overlapping (Schengen Area, European Union). Geographic information could point to multiple possible geographic positions of either certain value (Brest (France) or Brest (Belarus)) or uncertain value (‘Mum's house' or ‘the forest'), or a geographic location could point to entirely fictional places (‘Atlantis'). Some of these cases introduce specific challenges to visualization. Reviewing the existing visualization and interaction techniques for geospatial network data is the focus of our survey.

3.2 Related concepts

There are several concepts adjacent to geospatial networks in that they describe relationships or movements between different geographic locations. However, we do not consider all types of such data geospatial networks.

Firstly, it is useful to think about these concepts in terms of link continuity, which describes to what extent data about the trajectory of each link is available. In some cases, like GPS tracking or air traffic data, continuous physical routes between origins and destinations are available. Such data are called trajectories. Trajectories have very high link continuity. Other data might be structured such that full trajectories are not available but intermediate stops between the origins and destinations are recorded, such as parcel tracking data. Origin-Destination (or OD) data consists of only origin-destination pairs, with no information on the trajectory between the two locations. OD data has the lowest link continuity.

Secondly, it is necessary to consider to what extent the locations in the data (i.e. origins and destinations) represent network nodes. If locations are essentially arbitrary, for example in the case of ride-sharing data where a trip can start and end at any given location (as opposed to for example bus travel being limited to bus stops), each ‘node’ would only be connected to a single link. Here, further abstraction in the form of aggregating individual origins and destinations into areas would be necessary to form a meaningful network with nodes that have more than one link each. Data types with higher link continuity can be abstracted to data types with lower link continuity; for example, trajectories can be treated as OD data by ignoring the information about trajectories between origins and destinations.

In summary, OD, trajectory, and other geospatial data can often be interpreted as or abstracted to geospatial network data—which is why our survey contains several techniques intended for these data types—but not all OD or trajectory data should automatically be considered geospatial network data.

4.1 Collecting papers

Contributions to geospatial network visualization have come from many different fields including information visualization, graph drawing, and cartography. To account for the diverse range of publication venues for potential visualizations of geospatial networks, we followed a two-step approach. First, we looked at the proceedings and collections of major venues where work on geospatial and network visualization would naturally be published:

For each of these venues, we manually scanned the proceedings and retrieved candidate papers based on their title. Papers were included in this initial collection if their titles contained references to geospatial networks and their visualization. In an effort to obtain as many relevant papers as possible, we also included many papers where the title only mentioned either networks or geovisualization. We chose this approach because ‘geospatial networks’ are not a universally recognized concept, and many papers in our collection use different terms. The resulting variety in terms being used for similar concepts makes it problematic to identify relevant papers based on title or keywords alone. This resulted in a set of 191 candidate papers.

In a second pass we manually selected the most relevant papers out of the 191. To that end, we read the abstract and checked figures in each paper. This reduced our collection to 41 papers. From these 41 papers, we then extracted keywords, which were used to perform automated searches in the following online libraries which cover all major visualization and geographic journals:

The search terms (keywords) are a combination of different terms to describe geospatial networks and terms used to describe the visualization aspect. Terms were combined in a Boolean search query as follows:

(geographical network(s) | geographic network(s) | geospatial network(s) | spatial network(s) | spatial interaction data | origin-destination)

&

(visualization | visualisation | graph drawing | flow map)

This yielded a large number of possible papers. Again, we manually narrowed down the results of the search by examining at least the abstract and figures in each of the retrieved papers. In addition, a number of papers were discovered through following references of some of the already retrieved papers as well as recommendations from reviewers. This selection step yielded another 52 papers, raising the final number of papers to 95. A paper was included if both of the following criteria were fulfilled:

For example, we excluded an algorithm for clustering trajectories [AAFG18] or a technique for visualizing vessel movements [WvdWvW09] because while trajectory or movement data can often be abstracted to network data, it was not in the context of these techniques. Further, we excluded many edge and trail bundling techniques and instead selected a sample intended to represent the different possible types of edge bundling, which will allow for discussing implications for visualizing geospatial networks. In this survey, the term edge bundling encompasses both edge and trail bundling techniques, since the differences between the two categories are negligible in our context [LHT17b].

4.2 Creating a design space

Before arriving at our final design space, we went through several iterations of taxonomies and typologies, each one informed by the techniques themselves as well as alternative higher-level objectives. For all iterations, a structured coding of our collection of papers was performed by one of the authors, informing our assessment of how useful each approach is. For the final design space, the full collection was independently coded by two people and disagreements resolved through discussion afterwards. The full, coded collection is available on the website (geonetworks.github.io).

Version #1: Data-driven—Our first approach was to structure techniques by the data types a given technique can be applied to, for example directed or undirected networks, additional link attributes, or dynamic geospatial networks. This approach is informative for describing how specific visualization challenges are addressed by the literature. However, this approach did not provide informative insight into the visual characteristics of different techniques and help discuss conceptual ideas behind techniques’ design. We decided to discuss our grouping for #1 later in Section 10, complementing our design space.

Version #2: Technique-driven—Our second approach involved coding papers by grouping common visualization techniques for networks such as node-link diagrams, adjacency matrices, flow maps, etc. This is a common approach to classify techniques across the visualization community as it often leads to a high-level overview of major classes and ‘ideas’ of techniques. However, it did not yield insightful results as most techniques (66%) used node-link diagrams, most of which apply edge bundling. We were not able to derive a meaningful discussion about how a specific challenge motivates a specific design and what problems it is solving. Moreover, we felt we would fail to capture the richness of all the different visualization approaches and to list meaningful directions for future design.

Version #3: Challenge-driven—Our third intention was to create a taxonomy around which problems and challenges a technique addresses. We were hoping this would result in a practical resource of solutions to common challenges. However, we found that such an approach would suffer from three major drawbacks. First, a list of challenges is necessarily incomplete if not derived from a systematic schema. In other words, without a systematic approach to understand challenges in geospatial networks, any list would purely capture the state-of-the art and our ‘taxonomy’ would be outdated with the next technique proposing a solution to an unsolved (and hence not appearing in our taxonomy) problem. Second, we would potentially not be able to agree on the definition of a challenge. For example, visual link clutter is a problem of node-link diagrams, but not of geospatial networks themselves. For example, using adjacency matrices avoids this problem, rather than solving it. Lastly, a taxonomy based on challenges would not help to discuss and understand design solutions, decisions, and to potentially inform new designs. Together with Version #1, this informs our discussion of challenges, and techniques addressing them, in Section 10.

Version #4: Representation-driven—We eventually decided to code visualization techniques according to how they balance their visual representations at the tension between (i) explicitly showing all possible information in a geospatial network, that is all links, all nodes, all geographic information and places of interest, and (ii) managing visual clutter and information overload to provide for efficient task-oriented visual representation. We found our design space, dimensions, and classifications to best capture the trade-offs required in designing geospatial network visualizations and to provide a conceptual framework perhaps similar to the design space described by space-time cubes [BDA*17] or map-like visualizations [HHS20]. The complete rationale is given in Section 4.3.

4.3 Final design space

Our final design space consists of four dimensions and two sub-dimensions (Figure 3), each representing an essential aspect of a geospatial network visualization:

As we found techniques that abstract only one of both nodes or links, we classify techniques separately for nodes and links.

The dimensions and can be seen as two sides of the same coin: making decisions about the visual representation of network topology implies a decision on how to represent geography. For example, a visualization might choose to explicitly represent geography and maintain spatial distances between locations. This will most necessarily result in issues with node overlap if nodes are placed at similar or nearby locations. Or links overlap for the same reason and can stretch far over the geographical representation. On the other hand, a designer could choose to abstract geographic information, for example by distorting geographical distances to provide for better perception and understanding of a network's topology. Different visualization techniques propose different solutions to overcome this tension and abstract information in the network as we discuss in Sections 5, 6, 7.

Besides and , we include two further dimensions.

With this dimension-driven approach, we can capture the richness as well as some of the design decisions in existing techniques, while at the same time providing a design space to locate and compare existing techniques as well as inform discussions about missing approaches. Each dimension classifies techniques according to how much of that information (geography, nodes, links) they show explicitly, and how much of that information they abstract and aggregate. Along each dimension, techniques and designs are roughly grouped into categories, although transitions between these categories are fluent. The following Sections 5, 6, 7, 8, 9 detail each of these dimensions and discuss the types of representations, compositions, and interactions we found. A discussion on the limitations of this approach is provided in Section 11.

5.1 D1—GEO: Mapped

Mapped techniques are the most explicit geographic representations. In mapped techniques, geospatial locations are visually represented by positioning visual elements using a geographic map projection. Any map projection introduces distortion as it is impossible to flatten a three-dimensional surface into a two-dimensional map without any distortion [Sny87, p. 3]. However, different map projections preserve different features of the geography, for example angles, areas or some distances, and as such the choice of projection is always a trade-off between different kinds of distortion. In addition, the mapped category includes three-dimensional globes. We chose not to differentiate between two-dimensional and three-dimensional representations as separate categories in this design space because the distinction is not about 2D or 3D but about a consistent presentation of a geographical space. Distortion, as introduced in the next section, distorts a geographic space based on the network data and thus introduces a data-driven distortion. For example, 3D globe representations can be distorted in the same way as 2D maps, based on the network's topology [ASB07]. The majority of the surveyed techniques use mapped representations (74%).

Three-dimensional (3D) globe representations offer the most precise geographic information with respect to geographic area sizes and distances. 3D globes, either displayed on screens or in virtual reality (VR) [YDJ*19] (Figure 4(a)), have been used to display node-link diagrams in various forms, for example using straight lines on a globe [CEH96], arcs on a globe [MHCF96, YDJ*19, KB16], edge bundling around the globe [LBA10b, ZZLL18], or flow maps spanning a globe [DSD14b]. 3D globes preserve global distances and sizes of areas. Also, link crossings can be reduced since links can be drawn along their shortest path around the globe, naturally routing links around each other. The main shortcoming of globes is that, unless the entire network is located on one half of the globe, interaction is required for full exploration.

However, most mapped techniques use 2D maps, despite the different types of distortions introduced by different map projections (such as Mercator or others) [Bat09]. Still, 2D maps are highly usable on 2D screens and in print media. Many visualizations show geographic details such as roads [AAFW17] and country borders [ITH16]. Other techniques reduce geographic detail to country shapes [BSV11a] (Figure 4(b)) or remove any geographic detail except locating nodes at their respective geographic position on the screen [GHNS11, BW98].

The major advantage of mapped representations is that they support tasks related to a) purely geographic information such as Which regions are close? How far are these locations apart? Which country is this? Is there a mountain? and b) geographic information about the network topology (if topology information is provided properly by the network representation): Is this region well-connected? How far apart are these two nodes? Which one is the longest link in my network? A second advantage of mapped techniques is that people are familiar with geographic data being displayed on maps. Maps have been shown to have cognitive benefits when interpreting geographic data [HHS20].

The drawback of mapped techniques is that they cause problems when nodes are close or at the same position, or when links span large distances. Depending on zoom level, nodes will often be displayed off screen while at the same time being highly related to the currently visible nodes. Abstracting the geographic information through distortion, aggregation, or removing information can offer some solutions. Another issue present in all mapped node-link diagrams is the visual dominance of long links. A connection across continents is not necessarily more important than a local link (often quite the opposite), yet takes up much more space simply due to the geographic context, potentially covering shorter links as a side effect. This is further aggravated through the distorted distances caused by most map projections. Finally, mapped representations result in positional variables of nodes not being available for other information such as connectivity or node type.

5.2 D1—GEO: Distorted

Distorted describes techniques where geospatial locations are displaced with respect to their original position in the initial map projection—both 2D and 3D. As discussed in Section 5.1, any map projection introduces some distortion as a consequence of projecting 3D space onto a 2D plane, but the Distorted category deals with distortions based on the network data, either directly through data-driven algorithmic distortions, or indirectly through interaction techniques that let users distort the visualization to explore the network. Generally, distorting the geography is used as a way to show the network topology more clearly and avoid difficulties such as described in the last paragraph of the previous section.

For non-spatial networks, laying out nodes based on their connectivity is common practice. For example, force-directed layouts place nodes with strong connectivity (many connections and many common neighbours) closer together. For geospatial networks, there is an inherent conflict between using node positions to represent geographic locations and using them to expose the topology. Distorting the underlying map or displacing individual nodes has been explored as a compromise to address this conflict. Among the 20% of techniques that use distortion, we identified five main approaches, including both continuous and discontinuous types of distortion:

First, there are techniques that use continuous distortion to show alternative measures of distance instead of the geographic distance between two nodes [ASB07, BDD*16] (Figure 5(b)). Alternative measures of distance in this context could be for example travel times or dissimilarity measures.

Second, tile maps transform geographic regions into a grid of identical tiles, a form of discontinuous distortion. The tiles usually cannot be placed at their original geographic locations [MH17]. For example, OD maps [WDS10] use nested tile maps to represent geospatial networks. As illustrated in Figure 5(a), each cell contains a small version of the larger map. The colour of each small cell indicates the flow volume into that cell from the larger cell it is nested into.

Third, map insets are a form of discontinuous distortion. Map insets either contain smaller (undistorted) sub-maps at different scales from the main map [BKA*16, OHN*18] (Figure 15), or individual nodes [GRE11]. Insets scale parts of the map up or down, or move locations away from their original position, which we consider a form of distortion since it results in distances, areas and angles no longer being consistent across the map.

Fourth, there are representations where node positions are computed as a trade-off between showing the true geospatial location and clearly showing the network topology, usually using continuous distortions. Essentially, nodes are shifted to increase the legibility of the network representation. An example of this is centrality-based scaling [MG06], where the underlying geography is distorted such that dense areas in the network are enlarged compared to sparser areas, while preserving link orientation as much as possible. A similar method specifically for road networks is proposed by Haunert and Sering [HS11]. A notable application of this type of distortion are metro map layouts [e.g. HMdN06, WC11, BBDZ08, vDL19] (Figure 5(c)), a classic application of graph drawing. The common place of such transit maps is that users do not need to know the precise geography of the transport network—it is more important that they can clearly see how different lines connect so that they can plan their route accordingly. As such, a map that distorts the geography to the extent necessary to create an easily legible network map is an ideal trade-off.

Lastly, continuous as well as discontinuous distortion can be used as an interaction technique, scaling different parts of the network up and down based on user interaction. A fisheye lens [BMS93] is a classic implementation of this. For metro maps, a custom scaling method specifically for this purpose has been proposed [WC11]. Interaction techniques are discussed separately in Section 9.3.

5.3 D1—GEO: Abstract

An abstract geography representation encodes geographic information without the use of map projections. This usually includes non-spatial variables such as colour or shape (Figure 6) and can be seen as the exact opposite of explicit geographic representations. Often, geographic locations are aggregated into coarser groups. Note that a visualization can still use position to place visual marks on the picture plane, but in abstract geographic representations there is no natural mapping between an element's position on the screen and its geospatial location. Displaying locations along a line could be considered a projection from 3D to 1D, but it is not a map projection, which is defined as a projection onto a 2D plane [Sny87, p. 3].

Abstract representations allow for a great variety of designs and, we believe, offer many unexplored solutions as we only found five papers with abstract geographic encodings (5%). Two papers use circular chord diagrams [Hen13, AS14] (Figure 6 (b)) in which geographic information is encoded as groups of nodes along the circle (technically along a single spatial dimension, that is the circle's circumference), using colour as redundant encoding for geographic regions. A third technique uses a variation of arc diagrams termed Kriskograms [XC09] (Figure 6(a)), which orders nodes on a horizontal 1-dimensional straight line. Our specific example orders nodes according to their position from west to east but other encodings, for example grouped by country as in the chord diagrams are easily imaginable. In both examples, geospatial locations can be approximated with greater or less detail, for example locations on the Northern and Southern as well as Eastern and Western Hemisphere. A fourth technique is an adjacency matrix, in which nodes can be grouped by geographic location or region [BPLL11] (Figure 6(c)) or geographic regions being integrated into the network topology as individual nodes, for example a node for every location having links to the nodes related to these locations. Further examples of abstract encodings could include colouring nodes in a force-directed node-link layout based on their geographic location, for example country.

The dimension represents a continuous spectrum and provides the designer with many choices and opportunities. Decisions depend on the level of precision required for the geospatial aspect of the data. For example, if a task requires geographic fidelity (e.g. estimating spatial distribution, densities, and distances of nodes), then mapped representations should be naturally considered. If, however, a task can neglect certain geographic fidelity (e.g. estimating number of nodes in a given region), geographic information could be abstracted or distorted to provide space for visualizing information relevant to the task (e.g. distorting space to remove overlap between nodes to support estimating the number of nodes in a given region).

6.1 D2.1—NODE: Explicit

With 87% of the surveyed techniques, the majority of techniques show nodes explicitly, that is show each individual node in the network. In any of these representations, nodes can be shown explicitly as points (node-link diagrams, arc diagrams) or rows and columns (adjacency matrix) (Figure 7(b)). Sometimes, especially in techniques using edge bundling, explicit visual markers for nodes are omitted but node locations are still clearly identifiable from the endings of links.

Most techniques with explicit node representations are variations of node-link diagrams, differentiated only by the types of links they use (such as straight lines, arcs, bundled edges, etc.). These types of visualizations are typically superimposed on a mapped geography representation.

However, explicit node representations have also been used in combinations with both explicit and distorted geography. For example, Necklace maps [SV10] (Figure 7(a)) display nodes on a circle surrounding the relevant part of the map. Nodes are placed on the circle according to their geospatial position, resulting in a distorted display of the geography. A similar method is proposed by Stephen and Jenny [SJ17], where nodes that are out of view are laid out around a target area in a circular arrangement and connected to nodes in the target area (Figure 14(b)). The distorted globe by Alper et al. [ASB07] (Figure 16(b)) and deformed map by Bouts et al. [BDD*16] (Figure 5(b)) use explicit nodes on a globe/map, combined with an abstract link representation.

Combined with an abstract geography representation, we have found techniques that display nodes in a circular, spatially ordered layout, or on a single spatially ordered axis, with the network topology shown as a chord diagram [AS14, Hen13] (Figures 6(b) & 16(a)) or arc diagram [XC09] (Figure 6(a)).

6.2 D2.1—NODE: Aggregated

Aggregated node representations group individual nodes into metanodes and show only these metanodes explicitly. Aggregation can happen through grouping nodes in predetermined areas [Guo09], or more flexible partitions either through user interaction, for example specifying geographic regions [vdEvW14] (Figure 8(a)), or by algorithmically identifying dense clusters and grouping nodes by these clusters [LBW17b] (Figure 8(b)). The OD map [WDS10] (Figure 5(a)) uses a regular spatial grid or tiling, overlaid onto a 2D map and groups nodes within each grid cell. The volume of flows (link weight) between each pair of cells is then further encoded inside the cell using a nested map and colour.

Aggregating nodes reduces the number of visual elements displayed in the visualization. This can automatically reduce the number of links as they can be aggregated into metalinks, that is links between metanodes. In reducing detail, aggregation can highlight higher-level patterns and allows for showing summary statistics and data for each metanode (Figure 8(a)-right).

6.3 D2.1—NODE: Abstract

While aggregated representations still visualize network topology to some degree, abstract node representations do not show any visual marks that are identifiable as individual nodes or metanodes but rather communicate approximate locations and areas with fuzzy boundaries where individual nodes are situated.

We found five examples of abstract node representations (5%), all of which were created for flow data. Guo and Zhu use a flow-based density estimation method to extract patterns from the flow data [GZ14] and then show these patterns as flows on a map. The same authors propose a second, similar method, where flows are clustered based on similarity, and each cluster displayed as a single representative flow [ZG14] (Figure 9). Using these abstract techniques, the geographic representation can show location-specific information (attributes in colour) such as bandwidth or unemployment, instead of overloading the visualization with explicit or aggregated nodes. This information can be visually correlated with the flows while providing detailed geographic information. Similarly, Kim et al. [KJW*18] propose a combination of heatmaps, ‘field line’ maps (Figure 12(a)), and arrows superimposed on a map to visualize flows, whereas Yao et al. [YWZ*19] use hexagonal pattern maps to indicate directions (Figure 12(b)).

As these techniques show, abstracting nodes to fuzzy areas or glyphs can reveal overall patterns of how different areas are connected, especially for very large and dense networks. However, since any abstraction selectively hides some details of the data, the quality of the final visualization heavily relies on choosing methods appropriate to the data and task.

In summary, the dimension, similar to , represents a continuous spectrum that provides a range of possible design choices: showing nodes explicitly and with full detail, aggregating nodes into clusters and other meaningful groups, and eventually fully abstracting the visual node representation, focusing only on connectivity. The tasks supported by this range depend on the required detail about nodes; the less individual nodes are important, the more nodes can be abstracted and the visualization be designed for tasks focusing on, for example density, geographic landmarks, etc.

7.1 D2.2—LINK: Explicit

The largest group of techniques in this class are techniques based on node-link diagrams, which are largely differentiated by the visual representation of their links. A flow map is essentially a special case of node-link diagram, in which all links are weighted and directed, represented by arrows of varying widths. The simplest form of flow map uses straight lines or arrows to connect nodes, superimposed on a regular map. Particularly early computer-generated visualizations use this approach [e.g. Tob87, BEW95]. However, straight lines create cluttered maps even with comparably small data. As a consequence, a multitude of techniques have been developed to reduce clutter in node-link diagrams and flow maps, of which many are based on aggregation and as such discussed in the following section.

In smaller, less dense networks, clutter is less of an issue. Yet, links may overlap, or multiple links may connect the same nodes. To address this, several techniques have been developed to ensure links are clearly visible as separate lines. This can be achieved by bending them, for example using Bézier curves [BW98], which can be further spread out using angle constraints where the links connect to the nodes [BST00]. In three-dimensional visualizations, lifted arcs may reduce overlap compared to a two-dimensional display, particularly when the user can interactively navigate the visualization [YDJ*19, VFAA17] (Figures 4(a) and 10(b)). Kaya et al. [KB16] introduce a technique to spread out links around a globe.

In addition to reducing overlap, another challenge in node-link diagrams is the visualization of link attributes, which can be as simple as direction or weight, but also take more complex forms. When using arcs, the arc height can be used to encode data attributes such as link weight or distance [VFAA17] (Figure 10(b)). For networks with additional link attributes more complex than weights or directions, different modifications to the links have been proposed, such as animated link textures [RAB*18], where shape, size, colour and direction of particles moving along the links can be used to encode attributes. A static variant are patterned links [CKS*16].

In a flow map, each link would typically be represented by a line of uniform thickness, determined by its weight. An alternative to this are tapered links. In addition, there are different shapes and sizes of arrowheads that can be used [KLSC12].

Dynamic geospatial networks are networks that change over time. Changes can be limited to certain attributes, for example link weights, but can also affect the entire network, including new or deleted nodes or links. Dynamic networks can be visualized through animating node-link diagrams or displaying them as small multiples [BBL12]. Flowstrates is an alternative for data that can be represented as a directed, bipartite graph. The flows are displayed using two maps, one for origins and one for destinations. The two maps are linked through a heatmap showing the flows between the linked locations over time. Figure 13 shows refugee flows as an example, which change over time, and often go from one region of the world to another [BBBL11]. Displaying the network in a space-time cube is another method [KW05].

Node-link diagrams have been adapted to visualize uncertainty in the underlying graph data. Schulz et al. [SNG*17] introduce a technique that first decomposes the uncertain graph into its possible instances, then creates a visualization from these. Von Landesberger et al. [LBW17a] make further suggestions for visualizing uncertainty in geospatial network data.

A variety of interaction and navigation techniques have been developed for node-link diagrams. These are discussed in Section 9.3.

A different form of explicit link representation is used by matrix-based techniques, where each node is represented by a row and column in the matrix, representing outgoing and incoming flows to other nodes. Representing the network as a matrix requires the geospatial aspect to be displayed separately. This can be done on a juxtaposed map where colour-coding relates the locations to the matrix [Guo07]. For dense, directed, and weighted geospatial networks (often called many-to-many flow data), Yang et al. [YDGM17] introduce MapTrix, a technique that shows a matrix with a 45 rotation, rows and columns connected to their associated location on two juxtaposed maps (Figure 10(c)). As such, MapTrix employs the same basic concept as Flowstrates: inserting a graph representation in between two maps showing origins and destinations.

7.2 D2.2—LINK: Aggregated

Links are considered aggregated if they cannot be individually identified anymore. Aggregated links can be a good solution to overlap and clutter on node-link diagrams, and as a result many (28%) of our surveyed techniques fall into this category.

When nodes are aggregated, this nearly always leads to aggregated or abstract link representations because most visual representations remove, hide, or combine links between aggregated nodes. Examples are Van den Elzen and Van Wijk's technique for multivariate network exploration [vdEvW14] or Li et al.'s module-based visualization [LBW17b], both shown in Figure 8. However, the majority of aggregated link techniques we found use explicit node representations, aggregating the links only. Note that nodes can be aggregated while links are explicit: in such a case, individual links would be shown between clusters of nodes. However, we did not find such a technique applied to geospatial networks.

Edge bundling, for which numerous algorithms have been proposed, is a technique that bends links to form bundles [e.g. HvW09b, LHT17a, PHT15, PLCP12, GHNS11, CZQ*08] (Figure 11(a)). The level of aggregation depends on the algorithm and parameters that are chosen – if the bundling is very ‘loose’, with individual links clearly visible, the representation may in fact still be considered explicit. However, most edge bundling techniques generate clearly aggregated results, for example the 3D edge bundling algorithm by Lambert et al. [LBA10a] (Figure 11(b)). A more complete overview of edge bundling techniques is provided by Zhou et al. [ZPYQ13] and Lhuillier et al. [LHT17b]. Edge routing is an alternative approach that defines fixed routes that links must follow, effectively also bundling edges [BS15].

Flow maps, that is node-link diagrams with directed, weighted links, suffer from clutter problems even for relatively small data sets. Link weights are represented by line thickness, and arrow heads are added to each link to show its direction, resulting in thicker links easily covering up nodes and other links. This can be somewhat mitigated by changing the styling of the links and drawing thinner links on top of thicker ones [JSM*18], but nonetheless, straight-line layouts are severely limited. To mitigate this, different types of bundled flow map layout algorithms have been proposed: a layout based on combining edge routing and spline interpolation [DLY*05], a layout based on spiral trees [BSV11a] (Figure 4(b)), stub bundling [NB13], and a force-directed layout [JSM*17]. To create a layout similar to that of the original flow maps by Charles Minard [reproduced in [Ren18], Sun proposes a layout that routes links through oceans where possible [Sun19] (Figure 11(c)). Additionally, several ‘hybrid’ techniques between edge bundling and bundled flow maps exist. These techniques take account of the link direction when bundling spatially proximal links, for example, divided edge bundling which bundles flows in different directions separately [SHH11] or Graser et al.'s edge bundling-based flow map technique [GSRB19]. There are also flow map techniques developed for three-dimensional globes [DSD14b].

7.3 D2.2—LINK: Abstract

Abstract link representations are those that do not display each link as an explicit visual element. In general, we observe that abstract link representations are often used to visualize a specific aspect of the network data rather than provide an overview of the network topology in general.

Several techniques focus on visualizing the directional aspect of origin-destination network data. To visualize the direction of flows, Andrienko et al. [AAFW17] propose a technique where node locations are marked by glyphs, which show the strength of flows in different directions over time. Pattern maps [YWZ*19] visualize flows on a hexagonal grid which is superimposed on the geography. Each hexagon indicates the magnitude of the flow on its inside (grey), and the distance travelled on its boundary (red/orange) (Figure 12(b)). Kim et al. [KJW*18] propose a technique that generates ‘field lines’ to show flow strength and direction (Figure 12(a)).

Other techniques focus on showing the ‘connectedness’ or similarity of different nodes. The distorted globe technique by Alper et al. [ASB07] shows the node locations on a globe, distorting the globe such that nodes are closer together the more closely linked they are, without showing links as arcs or similar (Figure 16(b)). A similar technique on a flat map has been introduced by Bouts et al. [BDD*16] (Figure 5(b)).

Finally, several techniques exist that extract high level patterns from the network data. Andrienko et al. [AA11] developed a technique that at first glance, seems to show a regular flow map, yet not only makes use of nodes aggregated into areas, but also of partitioned trajectories such that flows are only drawn between neighbouring areas. The previously discussed techniques by Guo and Zhu [GZ14, ZG14] follow this pattern as well (Figure 9).

In summary, the dimension describes the spectrum of information shown for links. Explicit link representations support tasks about individual links (e.g. path following, link type, link direction), while aggregating links supports general connectivity tasks (e.g. high-level network structure, connectivity of regions). Abstracting links can help showing direction and strength of links without occluding any geographic features. This is helpful where geographic features or nodes are important, where nodes are very closely placed on a map so that space for visualizing links is scarce, or where a specific network metric (e.g. density per region) is important and can best be shown by showing meta-information about links and thus choosing a more abstract representation rather than displaying individual links.

8.1 D3—COMP: Juxtaposed

In a juxtaposition, network representation and geography representation are placed side-by-side on the screen as commonly done in Coordinated Multiple Views (CMV) environments. In a CMV system [Rob07, WWK00], views are meant to show complementary information and each view can act as selection tool to filter or select information for other views. Brushing and linking are common interactions for these systems. Typical examples for juxtaposed visualizations for geographic networks include the OD Wheel [LWLY15] and Ibarra et al.'s juxtaposition of a map and an arc diagram [ITH16]. Techniques that use multiple representations of either geography or network, for example a 3D globe and a 2D map [CEH96] or multiple perspectives on network topology [Guo09] do not count as juxtaposed in our survey.

To better relate elements across different views of network topology and geography, some techniques draw leader lines between locations and nodes, for example between regions on a map and rows and columns (the network's nodes) of an adjacency matrix [YDGM17] (Figure 10(c)). Another example of juxtaposition is Boyandin et al.'s Flowstrates [BBBL11] (Figure 13) which combines two geographic maps with a third visualization in between the two maps, showing changes in link weight over time. Each of the timelines in the central visualization is linked to the respective regions in both maps to provide for a network representation.

Juxtaposition strongly reduces visual clutter and allows for combining precise and mapped geographic representations with any type of network representation (node-link, matrix, etc.), at the same time allowing for explicit representation of nodes and links. However, as pointed out by Javed and Elmqvist [JE12], users need to build a mental mapping between the two representations. This can require extra mental effort, especially when multiple objects are targeted. Elements need to be connected across visualizations using visual elements such as lines or interaction such as brushing and linking. Also, the visual space is divided, so each representation has less visual space for presentation.

8.2 D3—COMP: Superimposed

In superimposed compositions, the network and geography representation are visually overlaid, in most cases the network on top of the geography. Superimposition can happen in that geography is seen as a reference for placing nodes at their precise geographic positions (Figure 14(a)) or as approximation for node positions (Figure 14(b)). It also does not matter whether geography is mapped or distorted, or abstract. As discussed in Section 5.3, in abstract geographies, geography can still be shown along a single spatial dimension while links are overlaid (Figure 6(a)). Still, the most commonly found versions of superimposition (55%) overlay explicit nodes on mapped geographies  [DLY*05, BSV11a, JSM*18, Sun19, YDJ*19] (Figure 4(b), 11(c) & 14(a)). Some techniques also superimpose abstract node representations on a mapped geography representation [AAFW17, YWZ*19] (Figure 12(b)).

An interesting variation of this approach is In Situ Exploration [HSS11], where the user can draw rectangular ‘portals’ onto the map and select a type of visualization, for example a matrix. The ‘portal’ inset then displays a visualization of the data of the region which it covers on the underlying map.

Superimposition can often be easier to interpret and creates less cognitive load for the viewer. However, superimposition has visual elements of both geography and network in the same visual space, which may easily produce visual clutter and might make it difficult to visualize additional attributes.

8.3 D3—COMP: Nested

In a nested representation, one of network or geography representation is nested inside the visual elements of the respective other representation (geography or network). One example of a nested representation is the OD Map by Wood et al. [WDS10]. An OD Map divides a geographic map into cells in a regular grid. Then, inside each cell, that is a confined geographic space, a small representation of the entire geographic space is nested (Figure 5(a)). Geographic regions on each of the small maps can now be used to encode information about the links between the region represented by the cell and each region on the miniature map. Hadlak et al. and Schulz et al. propose techniques that nest point-based tree representations of hierarchical data into geographic regions on a map [HTSS10, SHS11].

Another nested technique are shifted maps, which show geographic maps inside the nodes of a node-link diagram [OHN*18] (Figure 15). Nesting in shifted maps allows this technique to provide for a seamless transition between a geographic placement for nodes, and a geographic distortion that renders the maps’ visual (Euclidian) distances between the nodes on the screen depending on node connectivity using a force-directed layout.

Nesting creates compact representations and shows specific information about specific regions or nodes. However, there is usually limited space for the nested representations as nesting requires space to render the nested views which can then occlude information in the background (in the case of geography). Alternatively, nested views can get quite small. Moreover, extra efforts are required to understand the context, for example the distortion in OD Maps or the different scales of geography in [BKA*16, OHN*18], and to provide for a holistic view in the viewer's mind.

8.4 D3—COMP: Integrated

A technique represents an integrated view of network topology and geography if it is not possible to separate network topology and geography into two clearly distinct visualizations. The visualizations of both geography and network topology depend on each other in terms of layout or other visual mapping decisions. In other words, an integrated technique cannot be shown in a juxtaposition or superimposition.

For example, the chord diagram in Figure 16(a) [Hen13] can explicitly show the network topology, while nodes are grouped, placed and abstractly colour-coded according to their geographic locations. Geographic information is integrated into an explicit network visualization. Another example for integration are Xiao et al.'s Kriskograms [XC09] that show geographic information as node labels. The ordering of the nodes is a one-dimensional projection (not a map projection) of their geographic locations. Network information can also be represented by modifying a geographic representation. For example, Alper et al. [ASB07] use a distorted geographic representation to represent the network information (Figure 16(b)).

Integration reduces visual clutter even more than juxtaposition, as it does not need to split the display space between two components. However, in all integrated techniques we found, one of the components (either or ) is visually abstracted. Thus, people may find it difficult to interpret the abstracted component.

In summary, the dimension describes a spectrum of combinations of visual representations for and (from loose to strong integration). Juxtaposition reduces visual clutter by placing geographic representation and network representation side-by-side. But extra mental effort is needed to link them visually. Superimposition overlays one representation on top of another (usually on top of ). The two representations are intuitively linked, but the overlapping of visual elements usually introduces visual clutter. Nesting embeds one representation inside the visual elements of the other one, which results in compact designs. Integration fully utilizes the display space by combining the visual representations of and . However, the abstraction introduced requires more effort to interpret the visual representation.

9.1 D4—INTERACT: Not Required

Out of the surveyed techniques, 65% do not require user interaction. In many cases, this means that the technique generates a static image, which can optionally be enhanced with basic interactions like pan and zoom, scaling (parts of) the visualization up or down, expanding and collapsing parts of the visualization, or filtering for a subset of the data. While any technique in this category is usable without interaction, the extent to which it is useful varies among the techniques and between different data sets. In general, techniques that do not require interaction have two major advantages: firstly, computational complexity is less of a concern if the image only needs to be rendered once. Secondly, non-interactive visualizations can be used in contexts where user interaction is not possible, such as in print materials or displayed on public screens.

Some spatial generalization techniques [e.g. Guo09, AA11, CKS*16], that is techniques that derive a less detailed visualization from a more detailed one, can be used to create one-off generalizations for a display at a specific size and scale, but are also computationally efficient enough to be used as part of an interactively scalable map or other visualization that automatically updates the level of generalization based on the zoom level.

Edge bundling techniques also typically do not require interaction, though they can be enhanced with interactive features to explore bundles. The most common interactive tool for edge bundling techniques is relaxation, which lets the user interpolate between the bundled and unbundled views [LHT17b]. In addition to this generic technique, the creators of the SideKnot edge bundling technique [PLCP12] explicitly discuss the possibility of integrating the technique with the EdgeLens interaction technique [WCG03], which we include under Interaction Only.

Not all non-interactive visualizations are necessarily static images; animated link textures as proposed by Romat et al. [RAB*18] use animation to move particles along a network's links to indicate link weight (flow). Again, interaction is not required but could be added for playing and controlling the animations.

9.2 D4—INTERACT: Required

Techniques are labelled as required if the visualization requires user interaction to fully explore the data set because some parts of the data are hidden in the default view, for example to reduce visual complexity (24% of surveyed techniques).

For example, in three-dimensional globe representations [CEH96, ASB07, LBA10b] (Figure 11(b)), or in the GeoTime system [KW05], which uses a space-time cube, user interaction is required to navigate 3D space through rotation and view the complete visualization. Without interaction, the visualization hides important information (e.g. data on the other side of the globe). If the visualization requires configuration, it requires interaction. Most interactive visualizations are displayed on a regular screen, limiting interaction modalities to using a mouse or touch screen. Virtual reality, on the other hand, can offer rich interaction methods [YDJ*19] (Figure 4(a)).

Interaction is also often required in dealing with large data sets. Several techniques present the user with an abstract overview and let them selectively expand parts of the visualization. Li's module-based visualization aggregates nodes into meta nodes, which can be expanded to view the underlying network structure [LBW17b]. Hadlak et al. initially present an aggregated node-link diagram superimposed on a map, then let the user open up additional visualizations such as matrices to further explore subsets of the data [HSS11]. The opposite approach is to initially present the user with a detailed, possibly cluttered, visualization, from which they can select regions of interest that are then visualized in a more abstract, overview-type visualization [vdEvW14] (Figure 8(a)).

A second group of techniques rely on interaction as an exploration tool, for example through filtering the data [VFAA17], or selecting subsets of the data, which are then displayed in separate, superimposed or juxtaposed visualizations [HSS11, LMYH11]. The Flowstrates technique offers rich interaction capabilities, for example letting the user interactively select which origin and destination locations should be displayed in the central heatmap [BBBL11]. Some techniques create a visualization entirely based on user input, for example metro maps that are arranged with a focus on the user's travel route [WTLY12].

A third application of interactivity is morphing between different network layouts, which can be useful in relating a network to its geographical context. An example is OD morphing, which morphs a node-link diagram between an edge-bundled display and a geographically accurate one, where links are routed along their true route [LLC*19]. Another example are shifted maps [OHN*18] (Figure 15), where users can switch between different node-link layouts based on a mapped representation, and alternative layouts showing travel distance, travel time, and travel frequency.

9.3 D4—INTERACT: Interaction Only

Interaction Only describes techniques that are not visualization techniques in their own right, but pure interaction techniques. As such, they are intended to be applied on top of a visualization created with an existing technique. The majority of Interaction Only techniques are designed to be applied to mapped node-link diagrams and mitigate issues node-link diagrams frequently suffer from, such as overlap, link clutter, and varying densities.

A number of different lenses have been proposed to help manage clutter in superimposed compositions. The Fisheye lens distorts the entire visualization to allow for zooming into a region while still viewing the entire network [BMS93]. The EdgeLens [WCG03] and its 3D counterpart, the 3DArcLens [DSD14a], push links away from the cursor by bending them. This makes it possible to see nodes and the underlying map more clearly. An application-specific lens is provided by the Focus+Context metro map, which combines a detailed view of a small region of the metro map with an aggregated, simplified view of the larger network context [WC11].

There are techniques that give the user fine-grained control over moving and displaying links. Link plucking [WC07] lets the user drag groups of links to the side to reveal what is underneath. Riche et al. [RDLC12] present three techniques: interactive bundling, which lets the user select links to bundle together; link fanning, which lets users select a node around which links are then spread out so the user can see individual connections; and link magnets, to be placed by the user, which attract links in their vicinity (Figure 17(b-d)).

Lastly, there are techniques focused on navigation: Link sliding [MCH*09] snaps the cursor to a link and while dragging the mouse, slides the field-of-view along the link until it reaches the other end of the link. The same paper introduces another technique: Bring & Go, which, upon selecting a node in a network, brings all its direct neighbours into view, even if they are not located in the current zoomed-in view. The user can then navigate to any of the connected nodes by selecting it. Ghani et al. [GRE11] present a navigation technique based on small map insets (Figure 17(a)). A degree-of-interest function is used to determine which out-of-view nodes are most relevant; the selected nodes are then displayed in small map insets along the boundary of the map.

In summary, some visualization techniques propose solutions to reduce clutter in a static way, for example by bundling edges or distorting space to try to address a specific set of tasks. Such techniques are good for static visualizations (e.g. posters) or contexts where interaction is tedious or unlikely. However, they make decisions for the observer with regard to what information to show and in how much detail. Other techniques introduce interaction to allow for exploration of, for example cluttered visualizations, or filter for relevant information. This aims to support a broader range of tasks than static visualizations. Eventually, a range of interaction techniques (Interaction Only, Section 9.3) can potentially be integrated into visualizations to provide for specific exploration tasks, for example Link Sliding or the EdgeLens can be applied to Kriskograms, OntoTrix, or flow maps on a 3D globe alike.

10.1 Link and node attributes

Geospatial networks can have a variety of attributes associated with nodes and links. We consider four specific additional data attributes here: Most common are directed links and weighted links, which are usually visualized as node-link diagrams making use of arrows of different thickness (e.g. in flow maps). However, there can be node and link attributes beyond direction and weight.

Directed links: Out of the additional data attributes, directed links have received the most attention, most often in the context of visualizing flows between locations. In node-link diagrams, common options include arrows, tapered links, and animated links, although there is no clear consensus on which design is preferable, especially in a geospatial context. Holten et al. conducted a series of studies [HvW09a, HIvWF11] comparing different encodings for networks in general and recommend the use of tapered and animated compressed links. Koylu et al. [KG17] compared tapered links with arrows. They found that tapered links are only better for identifying long distance links. Jenny et al. [JSM*18] evaluated different designs based on tasks including reading flow magnitude and counting the degree of nodes. They found arrows outperforming tapered links significantly and provide three potential reasons: 1) the gradients of tapered links are inconsistent due to different link lengths, which is confusing; 2) links in flow maps are usually thin, resulting a very weak gradient; and 3) incoming flows are difficult to determine with tapered links.

An alternative to node-link diagrams are matrices. For example, MapTrix [YDJ*19] juxtaposes a matrix whose rows and columns are linked to two maps, one for incoming and one for outgoing flows. A matrix naturally visualizes direction since its rows and columns typically indicate origins and destinations, respectively.

Weighted links: Another common attribute of links is weight, that is a simple numerical value associated with each link (e.g. trade volume). Link weight in node-link diagrams is often visualized through width of the links. In geospatial networks, this can lead to obstructing important geographic and other information. Using colour-gradient encoding (light to dark) compared to link width has been found more effective and efficient in a controlled user study [DWCM18] for small geospatial networks; participants commented that maps using colour gradients are clearer than maps using line thicknesses. As an alternative to static maps, Romat et al. [RAB*18] use animated link textures to indicate link weight, while keeping all links to the same width. Their user study found that participants could discriminate up to six different values based on animated link textures, but that the use of particle patterns resulted a poor performance for a quick estimate yet was the best choice for accessing details. However, no comprehensive and comparative study exists so far.

Additional link attributes: In cases where links have additional attributes beyond simple weights and directions, colours are commonly used to encode categorical information. For example, Abel and Sander [AS14] use colour in links to represent regions of the countries in global migration. In transit maps, colours are usually used to represent different transit lines [WNT*20].

Additional node attributes: In many cases, nodes are represented as identical shapes (e.g. circles). However, there are scenarios that require representing additional attributes on the nodes. One common case is using the size of the node to encode a quantitative value. The quantitative value can be the net in/out flow into the geographic location the node represents, or a property associated with the geographic location but irrelevant to the network topology (e.g. the population of a country [SV10]). When it comes to the need of encoding more complex data on nodes, glyphs have been commonly used. For example, Yang et al. [YDGM17] place two semicircles on one location: one half represents net inflow and the other half represents the net outflow. Statistical charts can also be nested into nodes to visualize a variety of additional information [vdEvW14]. If node size is used to encode quantitative values on a mapped geography representation, small and close regions will pose a problem due to glyphs overlapping other glyphs, links, and potentially information on the underlying map.

10.2 Geographic locations

Our definition of a geospatial network includes networks associated with a variety of types of geolocations. We consider three different data type-related challenges. A rough division can be made into point locations (0D) and area locations (2D). For both of these location types, a multitude of techniques exist, with many techniques usable for both types. However, the distinction matters when addressing a common challenge related to locations: co-located nodes, that is multiple nodes at the same location (e.g. companies in the same building).

Co-located nodes are a challenge because placing multiple nodes in the same position leads to occlusion not only of the nodes, but also of potential links between them and surrounding geographical information. For near-identical positions, some distorted geography representations (see Section 5.2) can be used to mitigate this issue to an extent, though distortion cannot address exactly identical positions. The Vistorian [BRF*15] orders nodes from the same location on a circle around their position while the user interactively controls the circle radius (Figure 18).

When multiple nodes are located in the same area (e.g. a country), they could be juxtaposed inside this area, although we could not find a technique implementing this. Nodes might even be placed in an intelligent way that minimizes link crossings.

An approach that can theoretically be used for both point and area locations that are co-located is to detach the network topology from the precise geography to an extent. This can be achieved by using abstract or distorted geography representations, for example showing locations by grouping nodes occupying the same space into segments along a circle [AS14, Hen13], a line [XC09] or a matrix [BPLL11] (abstract) or compositions such as Necklace maps [SV10] (distorted), which arrange nodes on a circle superimposed on a map, with node positions based on geolocations as shown on the map. Rather than abstracting the geography, an alternative approach can be the use of a juxtaposed composition, which produces a looser integration of geography and network. An example is the MapTrix technique [YDGM17], which uses a matrix to display the network. Leader lines connecting the matrix to a juxtaposed map are used to link geography and network; these can easily link multiple matrix rows or columns to the same location.

The inverse challenge to co-located nodes would be nodes with multiple positions (e.g. if an organization has multiple offices in different locations). However, we are not aware of any techniques addressing this specifically for geospatial networks, or discussion of this challenge elsewhere. In non-geographic networks, this has been addressed by node-cloning [AvHK06], but this technique has not been adapted for geospatial networks and comes with its own set of challenges (e.g. showing which nodes are the same, deciding how to draw or duplicate links).

An additional potential challenge we see are node locations at different granularities, that is a network where some nodes are associated with geolocations at the level of countries, others with cities or precise street addresses. Similarly to the previous challenge, this is not a commonly discussed challenge, and we are not aware of any techniques addressing this.

10.3 Link density

In the context of link density, we consider two main data characteristics: Firstly, dense networks have too many links that cause visual clutter when visualized in node-link and arc diagrams. Superimposing a node-link diagram on a mapped or distorted geography representation will clutter the display and can make geography as well as the network unreadable. A different, but related challenge is posed by networks with varying density, where some geographic locations feature significantly more nodes and links than others.

A common solution for the visualization of dense non-geospatial networks are matrices, which scale to complete networks, that is networks where each node is connected to all other nodes (density1.0). Matrices have been extensively studied in visualization, starting with Ghoniem et al. [GFC04] who found that matrices scale well to larger network data. Matrices have subsequently been found more efficient for weighted and undirected networks [ABH*13]. In a crowdsourcing study, Okoe et al. [OJK18, OJK19] found that node-link diagrams worked better for topology and memorability tasks, while matrices were better for cluster-related tasks. However, it is challenging to integrate geographic information into a matrix. One solution is a juxtaposed composition in which leader lines connect rows and columns of a matrix to their associated geographic locations, shown on two maps [YDGM17] or grouped by location [BPLL11]. In a user study by Yang et al. [YDGM17], these two designs had similar performance and scaled better than bundled node-link diagrams superimposed on maps. An alternative solution is the nested composition of Wood et al.'s OD Maps [WDS10], in which the entire map is duplicated and nested into itself to resemble a map and thus represent the geographic context.

For applications where superimposed node-link diagrams are required, different methods exist to make these visualizations more readable and navigable even at high link densities. Edge bundling [e.g. HvW09b, LHT17a] or edge routing [BS15] can free visual space by visually grouping links, though this results in a loss of accuracy when following individual links [BRH*17]. Less problematic are techniques that keep links separate, such as manually routing links through ‘magnets’  [RDLC12] or automatically routing links around each other [BST00, BW98, JSM*17]. Two comprehensive studies found that curved links performed better than straight ones when superimposed on maps [JSM*18, DWCM18]. One of them, Jenny et al. [JSM*18] conclude that well-designed curved links can i) minimize the overlaps between links, ii) avoid them intersecting at acute angles, and that iii) curved links should be curved as little as possible.

Aggregating nodes is another option as it automatically leads to link aggregation as well. Examples are Li et al.'s module-based visualization [LBW17b], in which dense clusters of the network are visually represented by aggregate symbols, as well as the use of hierarchical clustering to aggregate nodes by Zhu and Guo [ZG14].

Moreover, rather than aggregating nodes or links individually, the entire network can be abstracted such that higher-level features of the topology are shown. Andrienko et al. [AA11] introduce an algorithm to generalize and aggregate directed geospatial networks such that a simpler version of the network is produced, which can then be visualized. A slightly different approach is Guo and Zhu's flow data smoothing [GZ14], which displays link-like arrows, but they are not connected to fixed nodes. Pattern maps [YWZ*19] indicate directions of flows in space through a hexagonal pattern; another technique by Kim et al. [KJW*18] uses a field line-like visualization for the same purpose.

While most of the above-mentioned techniques for reducing link clutter work globally on the entire network, other techniques have a local scope in that they resolve clutter for some nodes and links: dynamic edge lenses [Zou16], temporarily pushing away links [DSD14a], or topological fisheye techniques [BMS93]. Additionally, there are many generic graph interaction techniques which could be used for geospatial networks, such as the Local Edge Lens and Bring Neighbors Lens [TAvHS06]. These local interaction only techniques are good for keeping the overall visualization stable while exploring subgraphs and specific geographic regions. Also, while globally applied techniques can help to deal with non-uniform densities, local approaches like these do not unnecessarily sacrifice detail in less dense areas.

Finally, there are several approaches specifically useful for dense areas in networks with non-uniform densities, that is networks that also contain much sparser areas. One solution is using distortion to increase the size of dense areas, for example, through centrality-based scaling [MG06]. Metro map layouts [HMdN06] address this issue as well and could potentially be applied to non-transport networks as well. Interaction techniques that let the user view separate visualizations for subgraphs are also a possible solution [HSS11]. The problem can be avoided using an abstract geographic representation [AS14] or matrices to avoid positioning nodes based on their geographic location. Another solution to varying densities can be map insets [GRE11, BKA*16] which scale up particularly dense regions to reveal the network topology and are additionally able to bring subgraphs geographically closer, distorting geography.

10.4 Dynamic geospatial networks

Studying dynamic networks, that is networks that change over time as nodes and links appear or disappear or link weight changes over time, has led to many techniques, nicely summarized by Beck et al. [BBDW14]. Geospatial networks can involve a range of additional types of changes such as nodes changing positions and geography changing structure (e.g. when countries merge or split). While visualizations for geo-temporal (non-network) data have been summarized by Bach et al. [BDA*17], little is known about visualizing dynamic geospatial networks.

One common approach is to use animation to show changes. Juxtaposition of small multiples, one for every time step, is another straightforward method explored and evaluated by Boyandin et al. [BBL12]. Their study, comparing animation with small multiples, found that animation led participants to more findings with local events and changes between subsequent years. However, small multiples led to more findings concerning longer time periods. Animation can also be used with other types of visual representations, for example animating deformations of a 3D globe to show how strongly linked different locations are [ASB07].

For smaller networks with a moderate amount of time steps, where only the weights are dynamic, the Flowstrates technique [BBBL11] can be used. This technique juxtaposes two maps and a custom time series visualization such that the time series of each link is shown in the center, connected to start and end location on the two maps respectively. For some networks, using the third dimension to represent time, that is displaying the network in a space-time cube, may also be a solution [KW05]. For exploratory visualization, Hadlak et al. [HSS11] propose the concept of in-situ exploration of dynamic networks, where users can display and modify a variety of additional visualizations.

In cases where it is not necessary to explicitly show changes over time in sequence, temporal abstraction or summarization can be an alternative approach. Andrienko et al. [AAFW17] propose a technique to abstract dynamic network data over space and time, showing the result in a glyph-based visualization. Shifted maps [OHN*18] is a technique intended for personal movement data which includes network layouts based on how frequently someone travels to certain locations or how long the journey takes.

10.5 Uncertainty

Visualizing uncertainty in networks is an underexplored, but growing, field of research. In the context of geospatial networks, uncertainty can occur in different ways: Firstly, there is the issue of uncertain network topology, that is uncertainty about whether a certain node or link exists or what direction a directed link has. Secondly, there can be uncertain locations, that is where exactly a node is located, or in the case of geolocated links, what exactly their trajectories are. Lastly, nodes and links can have uncertain additional attributes. Uncertainty can be seen as ranging on a spectrum from exactly known via uncertain to unknown, and the grade of uncertainty will affect how it can best be addressed in a visualization.

We did not find any concrete techniques specifically for visualizing geospatial networks with uncertain topology or geolocations. However, Von Landesberger et al. [LBW17a] have proposed a typology for uncertainty in geospatial graphs, and identified many approaches to visualizing uncertainty that have not been explored or tested yet. They focus on modifying geolocated node-link diagrams to visualize uncertain graphs and thus do not consider solutions outside of what we call explicit geography and network representations. Also, techniques with an abstract geography representation, for example by using spatially ordered chord diagrams [Hen13, AS14], Kriskograms [XC09], or matrices [BPLL11], can be a solution for uncertain locations, since these techniques do not rely on precise geospatial locations to position elements of the visualization. The probabilistic graph layout introduced by Schulz et al. [SNG*17] is a technique to visualize networks with uncertain link weights or other numerical link attributes. The technique creates a ‘blurred’ node-link diagram by decomposing the uncertain graph into its possible instances, then visually recombining them using node splatting and edge bundling.

Overall, there is a clear need for a larger variety of techniques for more different use cases here. In particular, there is a lack of techniques usable for data exploration. Uncertainty in dynamic geospatial networks is another area that has not been addressed.

11.1 Design space

Our design space (Sections 5, 6, 7, 8, 9) provides an overview of various techniques’ designs with the goal of providing a conceptual understanding for possible design solutions. Following several iterative steps to classify techniques according to different schemata (Section 4.2), we eventually defined five design dimensions , :, :, , and . This design space was created on the premise that each visualization technique has to solve a trade-off between showing different levels of detail and precision for different types of information in order to deal with the complexity of data in geospatial networks.

To that end, each of the dimensions , , and describes a spectrum to categorize techniques according to how much information they show explicitly and how much information about the data gets abstracted and aggregated. We classified techniques from each paper into rough categories along these dimensions. This allows us to capture essential steps along the dimensions and their individual characteristics. Our dimensions and exhibit more discrete categories along their respective dimensions—loose to tight integration for and not required to interaction only for since these two dimensions naturally fall into more discrete steps.

We want to emphasize that all our dimensions are to be understood as a continuum between two respective poles. Such a continuum has three benefits:

In that sense, our design space is complete for the papers we could find, and we believe it is open enough to capture a range of future techniques.

11.2 Design space coverage and open designs

Our design space allows us to discuss existing and common designs (Figure 19), less common and underexplored designs, drawbacks of individual designs, trade-offs between designs along the same dimension, as well as to negotiate trade-offs between design solutions across dimensions.

Common combinations in our design space include Mapped Explicit Nodes Superimposed (53%) as well as Aggregated Links Superimposed (27%). The latter contains nearly all edge bundling techniques as well as flow map layout techniques. In contrast, other combinations have only a few associated techniques, such as Abstract Nodes Abstract Links (2%). We believe that many of the rarer combinations are underexplored but possible; for example, we can imagine abstract nodes juxtaposed with a mapped or distorted geography representation. We also believe there is a large unexplored design space of juxtaposed and linked visualizations where the network can be represented in a clearer way while the geography is mapped. MapTrix [YDGM17] and Flowstrates [BBBL11] are examples of techniques in this space.

However, our design space is descriptive, rather than prescriptive. In other words, we can point to holes in the design space, for example we could not find any techniques for a combination of juxtaposition and abstract geography. However, we cannot prescribe how a new technique should be designed. This is different from prescriptive design spaces which can be used to create new techniques by combining a set of options (e.g. layout, interaction technique, colour encoding, etc.). The dimension with the most prescriptive power is as our categories (juxtaposed, superimposed, nested and integrated) are quite distinct and generic design solutions. However, the categories for nesting and integration, for example, both capture a range of possible techniques and are hence less useful to describe a specific visual design. Likewise, while juxtaposition and superimposition present very specific design solutions, their individual implementation offers a wide range of design parameters. For example, a juxtaposition needs to clarify the size of each view (e.g. large geographic view and small network topology if the network is rather small but spatially unequally distributed), as well as mechanisms for connecting information across both views (e.g. brushing and linking, visual links, or consistent visual encodings).

11.3 Discussing techniques

Our design space makes it straightforward to discuss conceptual advantages and drawbacks of specific designs. Techniques on the explicit end of the dimensions show more explicit and, as a consequence, often more detailed information. Generally, techniques on the abstract end show less detail and aggregate and abstract information appropriate to specific tasks. Less information makes tasks related to individual nodes, links, and geographic locations harder or impossible. Generally, abstracting information is useful in two scenarios: (i) support tasks that require abstractions (e.g. analyse nodes and connectivity per geographic region) and (ii) hide information less important to a task and that would otherwise clutter the interface.

: Mapped techniques such as a 3D globe or 2D projected maps offer high precision regarding geography but pose constraints on the position of nodes—if used in a superimposed or integrated way—or require linking information between views if presented in a side-by-side view. 3D globes also require navigation. In general, distortion is an inevitable consequence of transforming a sphere or an ellipsoid onto a plane. It is impossible to unfold the Earth onto a planar map without distortion [Sny87, JŠA*17]. This can result in exaggerated and unequal link lengths for superimposed node-link diagrams, but also can result in a false perception of where a link is located, if that matters. Using three-dimensional globes [CEH96, KB16, YJD*18, YDJ*19] partly addresses this issue, but virtual reality is not always accessible.

and : Explicit network topology (nodes and links) combined with explicit geography is required in tasks that require parallel understanding of network topology (node connectivity, path following, clusters, identifying network motifs [LPP*06]) and precise geography at the same time. It can also precisely preserve the geography. However, the resulting views are usually visually cluttered.

: A loose integration (juxtaposition) is flexible, if not agnostic, to the respective representations of geography and network topology. Both facets can employ a visualization technique that best supports the information shown and the task at hand. As mentioned earlier, juxtaposition requires mechanisms to relate information from both views. Superimposition represents a stronger integration as network and geographical information are displayed in the same visual space. Most commonly, nodes are placed at their associated geographic positions. This might support tasks related to nodes and their positions as well as questions of local connectivity. On the downside, superimposition comes with the common issues that motivated this survey: node overlap, long links, ambiguous links, visual clutter, and the general difficulties to understand network topology. A visual solution includes moving nodes away from the map, presenting a transition to a juxtaposed view [SV10]. Interactive techniques (e.g. EdgeLens [WCG03], Bring & Go  [MCH*09] or node circles [BRF*15]) can further alleviate these issues. Some network representations, for example adjacency matrices, are hard to superimpose since node positions are constrained to vertical and horizontal rows and columns. Hybrid techniques such as NodeTrix [HFM07] superimposed on a map could provide a solution for analyzing local clusters and inter-regional connections. Nested and integrated techniques provide for a tighter connection of topological and geographic information, but the tight integration also reduces flexibility in choosing geography and network representation separately.

: Without interaction, a visualization needs to be very careful about clutter reduction and can present only a single visual representation. Interaction could allow for ‘moving along’ the dimensions in our design space, for example by morphing from a mapped via a distorted to an abstract geographic representation. A range of interaction techniques have been created to address specific issues. Interaction for exploring geospatial networks is a largely underexplored space in which we see great potential for novel techniques.

11.4 Negotiating trade-offs

Knowing our design space and the individual drawbacks of each category along the dimensions helps negotiate trade-offs between each category as well as think about hybrid techniques. For example, one possible way to address the trade-off between geography and network topology is to morph between geographic and force-directed layouts, or to restrict geographic information to the node neighbourhood [OHN*18]. Another possible trade-off is geographic distortion [BDD*16, ASB07] whereby through sophisticated geometric transformations geographic locations are relaxed and distorted to bring nodes closer to their positions in a force-directed layout. Hybrid approaches in terms of positioning, such as the approach taken in metro maps, are another way of giving more importance to the network topology.

11.5 Limitations and possible extensions

Some techniques in our collection caused more discussion when classifying than others. While mapped techniques with explicit nodes and links are easy to classify—perhaps due to the tradition our community has with node-link diagrams—techniques aggregating nodes and links were less common and consequently caused us more discussion in understanding and capturing their idea. Other ambiguous cases are found between distorted and abstract geography, as some abstract designs, like spatially ordered nodes on a circular chord diagram, could also be seen as extreme distortions. Still, we see the flexibility of our design space as a strength.

Future analysis of our collection of techniques may classify them differently. For example, in Version #2 of our taxonomy (Section 4.2), we tried to classify techniques by visualization types for networks (e.g. matrix, arc diagram). While we found that such a categorization does not capture the information necessary for our discussion, we believe such a categorization might still be useful to inform novel techniques in a more prescriptive way. However, care must be taken to not restrict creativity and to capture all possible groupings and combinations of geography and network topology.

11.6 Addressing open challenges

Section 10 provided an overview of how specific challenges, grouped by data type, are addressed in current techniques. Despite our survey including techniques from 95 papers, there is a large array of unsolved challenges in visualizing geospatial networks. For example, among the challenges most under-addressed is uncertainty. While uncertainty in networks is generally under-addressed, we could not find solutions for visualizing multiple positions, missing node positions, missing locations on links (trajectories) and the range of uncertainties present in geographic visualization.

We also found few techniques directly addressing problems in node overlap and resolving ambiguity when links overlap. Routing seems to be promising here but future routing algorithms could try to take geography more into account, to route links, for example through empty space or along semantic trajectories such as rivers or frontiers. Finally, techniques for dynamic geospatial networks, including nodes moving between locations, a changing network topology as well as other changing node attributes are under-explored. Approaches from spatio-temporal visualization [BDA*17] could help finding appropriate solutions.

11.7 Towards a task taxonomy

Much of our discussion in this survey is making reference to tasks. Tasks are a powerful concept in visualization that inform design and evaluation and have been formulated for networks in general [LPP*06] and dynamic networks [BPF14, KK17] as well as for geographic visualization [Rot13]. The latter taxonomy included objectives (identify, compare, rank, associate, delineate, procure, predict and prescribe) and seventeen operators (import, export, save, edit, annotate, re-express, arrange, sequence, re-symbolize, overlay, pan, zoom, re-project, search, filter, retrieve and calculate). However, such tasks are similar to generic taxonomies in visualization  [AS04] and do not provide the expressiveness necessary for geospatial networks.

More specifically, Andrienko et al. [AA06] formalized tasks for spatio-temporal visualizations, considering space, time and objects as fundamental elements and tasks as queries for the information associated with them. Yang and Goodwin [YG19] interviewed domain experts who analyse geospatial networks in their professional work and identified three analytical targets: single flow (i.e. a flow between two geographic locations), total flow (i.e. all flows linked to a given location) and regional flows (i.e. flows between locations within a geographic area). However, these works only focus on single perspectives of our design space.

To the best of our knowledge, a structured task taxonomy for geospatial networks does not exist yet. Such a task taxonomy could help to standardize evaluation and allow for comparison across technique papers, and additionally to characterize systems in terms of task support, thus allowing for more informed technique selections for applications.

11.8 Empirical evidence

Empirical evidence on how specific geospatial network visualization techniques perform is sparse (7% in our collection). Existing papers include mostly case studies, sometimes small quantitative user studies. The tested tasks are predominantly rather basic, with more complex tasks rarely being evaluated. Even when there is a stronger focus on evaluation, comparison across publications is practically impossible due to the lack of standardization. Our design space might provide some scaffolding here. For example, open questions that should be addressed by empirical evaluations include the effectiveness of geographic distortion and the impact and readability of abstract geographic representations.