Overview with details for exploring geo-located graphs on maps

Abstract

Geo-located graph drawings often suffer from map visualization problems, such as overplotting of nodes as well as edges and location of parts of the graph being outside of the screen. One cause of these problems is often an irregular distribution of nodes on the map. Zooming and panning do not solve the problems, as they either only show the overview of the whole graph or only the details of a part of the graph. We present an interactive graph drawing technique that overcomes these problems without affecting the overall geographical structure of the graph. First, we introduce a method that uses insets to visualize details of small or remote areas. Second, to prevent the subgraphs within insets from overplotting and edge crossing, we introduce a local area re-arrangement. Moreover, insets are automatically drawn/hidden and repositioned in accordance with the user’s navigation. We test our technique on real-world geo-located graph data and show the effectiveness of our approach for showing overview and details at the same time. Additionally, we report on expert feedback concerning our approach.

Keywords

Graph visualization networks geographic networks spatial data navigation focus+context

Introduction

Many real-world objects have inherent geographic location, which plays an important role in their visual analysis. For example, sensors measure geographic location of persons (e.g. cameras with geo-sensors, Global Positioning System (GPS) trackers), which is then used for travel analysis. Also, geographic location and distribution of factories plays an important role in supply-chain analysis.

Many geographic objects are connected, which creates geo-located graphs. In these graphs, each object is a node, and the connections represent edges. Examples of geo-located graphs are as follows: Internet (computes connected in a global network), travel graphs (i.e. routes between visited places), or supply-chain networks (i.e. transportation of materials between factories).

The analysis of geo-located graphs includes exploration of both the connectivity and geo-location of nodes. Interactive visualization is often employed as it enables an easy examination of graph structure and other graph properties. A common way to visualize geo-located graphs is by using a map displaying (a part of) the world, with the geographically correctly placed nodes and edges between nodes. While common map-based visualizations work well for smaller graphs with diverse node locations, they often fail for graphs with specific node distributions (see Figure 1). Especially, for graphs which are connected by many points in small dense areas, whereby these areas may be widely spread across the globe. For example, a supply-chain network with many factories in several cities, which are connected by transatlantic good transportations. In such cases, two visual presentations are commonly used. The first approach uses a large-scale visualization showing the whole graph. It leads to loosing details within cities and connectivity information such as which factories share a transatlantic connection (see Figure 1(a)). Alternatively, the user may zoom in and look at the details of a selected city, but then the overview of the whole graph structure is not visible (see Figure 1(b)). Also, other available graph drawing methods provide only limited support for this problem (see section “Related work”).

Figure 1.

Example problem—example supply-chain network consisting of 15 factories and 19 transportation routes: (a) at global scale, nodes and edges in dense areas are not visible because of local clutter and (b) when enlarging one area, distant parts of the network are not visible as they are located outside of the current view.

We present a new way of drawing geo-located graphs, which displays the overall geographical structure of the graph and is still able to show details and connectivity information between the nodes. Our approach is based on the notion of insets.¹ We enhance insets with graph-based extensions and introduce local area re-arrangements for graph connectivity exploration. We use insets for geo-located subgraphs to visualize details of small dense areas on the screen or of remote areas outside of the current view. In this way, the user can observe the overall data distribution and local details at the same time (see Figure 2). Furthermore, we propose to avoid clutter in dense areas by graph-based local position distortion. This local area re-arrangement focuses on readability of graph structure in small areas, while it shows approximate node locations in small areas.

Figure 2.

Our approach for visualizing a worldwide geo-positioned network. On- and off-screen insets show details for those areas, which are either too dense or lay outside of the current view. Insets are enhanced with graph-based local position distortion in order to enable the exploration of the graph structure.

Our work has the following contributions:

We present enhanced insets for showing dense areas in detail. The insets are positioned in a non-overlapping way, possibly close to their original position on the map. The insets for areas outside of the current view also indicate the distance and the direction of the original area.

The insets are extended with graph-based local distortion, which enables graph structure readability. It minimizes overplotting and edge crossings in dense areas, where the graph could be difficult to understand when using original geographic positions of nodes.

For scalability reasons, we also include interactive graph aggregation. The user can expand and collapse graph nodes and insets on demand and show them in insets.

We support full interactivity with automatic repositioning and hiding/showing of insets during graph exploration (e.g. panning and zooming). For example, if user zooms into an area of the inset, the inset automatically disappears and reappears after panning or zooming out.

We apply our new approach to real-world data on computer networks as well as geo-located graphs extracted from people’s traveling diaries. These datasets show the advantages of our approach for showing geo-located graphs. Expert feedback underlines the advantages of our approach for the analysis of real-world data.

The article is structured as follows: section “Related work” presents related work. Section “Approach” describes our approach in detail. Section “Use cases” shows two use cases using real-world data and includes feedback from two experts that evaluated these use cases. Section “Discussion” discusses the contributions and limitations. Section “Conclusion and future work” concludes and outlines future work.

Related work

We now present an overview of the most relevant work to our approach. For a broad overview of graph visualization techniques, we refer to Herman et al.,² Von Landesberger et al.,³ and Guo et al.⁴

A subproblem of general graph visualization is the visualization of graphs with geographic location. These graphs are also often referred to as flow-maps. Several techniques have been developed to improve visualization of these flow-maps: important examples include partitioning,^5,6 origin-destination (OD) maps,^7,8 or, as an alternative type of visualization, line density surfaces.^9,10 Many of those techniques try to improve problems caused by cluttering of very large graphs, for example by sacrifying details or changing the overall structure of the graph. However, these techniques do not specifically address the problem of smaller graphs with dense areas.

In the following, we focus on techniques applicable to sparse graphs that preserve the overall geographic layout. Related works can be coarsely divided into three main categories: distortion-based techniques, techniques with special treatment of off-screen elements, and techniques using interaction. They are discussed in the subsequent sections. Besides these techniques, there are also approaches from Hadlak et al.¹¹ and Javed et al.¹² that try to integrate or extend the existing techniques. These extensions, however, provide only limited mitigation of the below-mentioned general problems of the base techniques.

Distortion techniques

Distortion-based techniques draw the data on a screen in a space-efficient way. They allocate large screen areas to the data with the need for high level of detail and shrink regions with few details. Two main types of distortion exist: local distortion relying on user interaction, for example, fisheye lenses,^13,14 and global “static” distortion such as space folding.¹⁵

A prominent example of local interactive distortion techniques are fisheye lenses.^13,14 A survey of different lenses including fisheye can be found in Tominski et al.¹⁶ The lens enlarges a single user-selected area. It allows the user to explore the graph interactively by defining locations of interest. Lenses are also effective for resolving edge crossings.¹⁷ Interactive lenses may lead to difficulties with distance estimations even when looking at small areas, where distance distortion by map projections usually is negligible. This is caused by smooth transitions. Gutwin¹⁸ presented an improved fisheye lens by speed-coupled flattening. This allows the user to better estimate the distances during cursor movement. However, the distance estimation problem prevails for static images.

In comparison to detail+overview techniques, lenses such as the fisheye lens lead to less accuracy.¹⁹ Moreover, they require permanent user interaction. A detailed exploration of a larger dataset can be very time-consuming and tedious, or the user is constrained to exploring only a part of the dataset possibly disregarding important details.

An extension of fisheye lenses are multi-focal lenses²⁰ that can be used for graphs that have several points of interest at the same time. The interesting locations can be displayed by splitting the screen and displaying each part in its own window. However, this approach does not preserve the global geographic context of the windows.

Global distortion techniques deform the whole graph in an automatic way so that important areas use more space and irrelevant parts are compressed. In contrast to the fisheye lens approach, no direct user interaction is required.

A leading example is space folding.¹⁵ It shrinks areas of low interest in favor of the important areas by folding the map and the superimposed graph like a paper. In this way, the user can still roughly estimate the distances between the plain parts by looking at the folds. However, the different areas of interest must share either the same width or height before transformation. This makes this approach inappropriate for areas that have a very different scale. Furthermore, if the space between the areas is too large, the fold gets very deep.

Global distortion was used also for non-graph cartographic data: Bak et al.²¹ distort the map and the data in a way that each geographic area occupies an amount of space proportional to the number of nodes it contains. This technique focuses on scatter points, not on graphs. The effects of the extension to graphs are unknown. Sundarararajan et al.²² use multiple fisheye lenses to enlarge multiple parts of a graph that can have an arbitrary polygonal shape. However, the parts and their shapes are determined by an algorithm and cannot be easily chosen to fit different needs of different users. In these two approaches, distances between nodes on a distorted map are very difficult to estimate, because the different scales and smooth transitions are used. This is feasible for point datasets with no relations between nodes or relations where the length does not carry information. However, it might be inappropriate for graphs with important edge distances, such as logistic networks (assumed that edges are not distorted significantly by a map projection). Moreover, these approaches may cause too much distortion on a map by a very unbalanced graph. This might result in a distorted map, where the users do not recognize the original geographic regions anymore. In general, all the above-mentioned techniques do not specifically address the problem of possibly extensive edge crossings due to geographic position of nodes.

Awareness of off-screen targets

This group of techniques addresses a common problem of panning and zooming for navigating in large graphs: loss of information about objects outside the screen view (i.e. off-screen targets). During navigation, parts of the graph can move out of the visible view. This may lead to loss of information, as the users may forget details about the parts of the graph which disappear from the screen. Several techniques have been introduced to overcome this problem: proxy elements, halos, and insets.

Frisch and Dachselt²³ introduce proxy elements indicating off-screen targets. Proxy elements are located at the view border. The authors present several ways to display and organize them. However, their article focuses on the visualization of Unified Modeling Language (UML) diagrams. This solution might produce problems for graphs on a map, since the geo-location information in the form of the map surrounding the nodes also carries important context information, although it is not directly part of the graph. Also, it does not consider distances of the targets, since this is not important for UML diagrams.

Halos are also used to indicate the presence as well as the distance of off-screen targets (nodes in our context).^24,25 Users can assess the distance of the off-screen target by looking at the degree of the halo’s bending. While it provides an intuitive way for distance estimation, this approach focuses only on the awareness of targets. It does not show connections between them.

Insets are another way of showing distant nodes and a small part of their containing area at the border of the view area.¹ This is useful for nodes shown on a map. Insets allow the user to zoom at detail level without missing information about nodes that are out of view. In contrast to the fisheye views presented above, there is no transition between the selected area and the rest of the graph. Since a large number of nodes cause overplotting, the insets that are shown in the view need to be selected by a degree-of-interest function. The presented insets have several drawbacks: because an inset only shows one node at a time, the inset’s scale needs to be selected carefully. If too large, an inset might show the same part of the map as another inset. This leads to a possible misinterpretation of the data. As each inset contains one node, it gives the illusion that there is no other node in its area. If the insets are too small, they do not show enough context of the surroundings and so might fail their purpose. Our approach is inspired by this idea and extends it in several ways to overcome these problems (see section “Approach”).

A similar idea to the inset windows is presented by Thudt et al.²⁶ They create map segments with parts of a trajectory graph that are from special time periods and special areas. These segments are then arranged in the form of a timeline. However, the time dimension is very important in this approach, because it focuses on spatio-temporal trajectory data, not on generalized spatial graphs with complex structures.

Interaction-based techniques

User interaction is important for exploring larger datasets. There are a number of specialized interaction techniques for navigating the graphs.^2,3,27 We focus on techniques that allow awareness of and interaction with distant elements (e.g. neighbor nodes located in a far distance off the screen). Note that fisheye lenses^13,14,18 are also forms of interaction. We discuss them together with distortion techniques above.

Tominski et al.²⁸ present an approach that improves the awareness of neighbor nodes by providing a lens that first filters the underlying edges that are not connected to the selected node and second brings connected nodes into the lens area to improve their exploration. This is related to techniques for non-graph data. Baudisch et al.²⁹ show far located elements near the cursor when interaction with these elements is needed. Bezerianos and Balakrishnan³⁰ provide a circular widget allowing the user to indicate the direction of elements he wants to interact with. In this way, the user can avoid clutter caused by a large number of elements to interact with.

Moscovich et al.³¹ present two interactive approaches for navigating with a geo-located graph on a map: the so-called link sliding and bring and go. Link sliding is an easy way for a user to follow an edge without the risk of loosing the panning direction, slowing down, or following the wrong line at an intersection. It improves the way people pan through the map, but does not solve the need for panning through graphs with large distances between nodes.

Bring and go temporarily shows the neighbors of a user-selected node in close proximity for an easier and a faster navigation. This allows the user find a node he wants to navigate to without using panning and zooming. However, the information about the original location of the nodes is not shown. Also information about the original distance between the nodes and the view is neglected.

All previously presented approaches possibly require interaction with elements in order to get awareness of off-screen objects. They support the user in exploring interesting parts of the graph more easily. However, they do not guide the user to the interesting parts. So a user still could overlook parts that carry important information. Since permanent interaction is required to explore the graph, the approaches mentioned above also do not produce a static result in the form of a “finished” view, making it impractical to make a simple screenshot for uploading on a homepage or to create a graphic to be used in printed media.

Approach

In this section, we present our inset-based approach to support visual exploration of geo-located graphs with groups of nodes spread over a large area. It shows both an overview of the data and details in dense areas. Our approach supports interactive data exploration by automatic adjustments of the insets according to the current data view.

We introduce two types of insets suited for showing details of areas outside of the current view and details of small overcrowded areas on the screen (see section “Insets”). For exploring graph structure, we enhance the insets with graph-based local distortion (see section “Graph-based local distortion”). The insets support interactive visualization in various ways (video available at http://www.gris.tu-darmstadt.de/research/vissearch/projects/GeoInsets/index.html). To automatically determine the “areas,” we apply a hierarchic aggregation technique on the graph that is explained in section “Geo-located hierarchic graph aggregation.” We implemented our approach using JUNG library³² and use map images from http://www.openstreetmap.org/index.html.

Base data pre-processing and visualization

Geo-located hierarchic graph aggregation

Aggregation is commonly used for graph visualization.^33–35 Aggregation groups related nodes into the so-called super nodes, which are connected by aggregated edges (i.e. “super-edges”). Aggregation reduces the size of the data and thereby mitigates clutter and overplotting problems.

Inspired by Guo,⁶ we apply a dynamic user-steerable graph aggregation based on a hierarchic organization of the nodes. The hierarchy is determined by the political–geographical regions (i.e. continents, countries, counties, cities). Geo-political aggregation ensures a stable, reproducible, and intuitive grouping of the nodes irrespective of the underlying dataset. Alternatively, hierarchical or non-hierarchical clustering methods such as DBScan³⁶ can be used.

Figure 3 shows an example input graph (Figure 3(a)) and an aggregated graph (Figure 3(b)) grouped by continents. Each super node is located in the geographical center of its grouped nodes. Super nodes are marked red to be distinguished from normal nodes in blue. The size of the super node indicates the number of nodes it replaces. Super edges are color-coded according to their end nodes. Black edges connect normal nodes, red edges connect super nodes, and black-to-red edges connect a normal node with a super node. Edge thickness shows the number of edges grouped.

Figure 3.

Geo-based graph aggregation: (a) original graph and (b) aggregated graph according to continents.

Base visualization using proxy nodes

Inspired by Frisch and Dachselt,²³ we employ proxy nodes to indicate nodes that are out of the screen (see Figure 4) and to enable the user to select graph parts to be shown in off-screen insets (see section “Interaction”).

Figure 4.

Proxy nodes at the lower screen border indicate nodes that are outside of the current view.

Proxy nodes are always located at the screen border. They have a triangular shape. The shape should resemble an arrow pointing in the direction of their real location. The color coding is the same as for other nodes: blue: original; red: aggregated nodes.

Insets

Our approach is based on so-called insets, which we enhance for showing geo-located graphs. Insets show details of graph parts, which are either outside of the current view or are cluttered (too small and dense) in the current view (see Figures 1 and 5).

Figure 5.

Inset example.

We extend the insets presented in Ghani et al.¹ Our insets show a subgraph of nodes instead of single nodes. The subgraphs in the insets have nodes that are geographically related to each other. The geographic relation is given by the geo-political graph hierarchy (see section “Geo-located hierarchic graph aggregation”). Therefore, an inset is equivalent to a cluster. The level of detail is data- and user-dependent. For example, an inset may show the part of the graph located in the United States, in Massachusetts, or in Boston, depending on the user’s interest. The user can change the level of detail interactively in the view (see section “Interaction”).

Inset design

An inset is a small window with a map showing the location of its member nodes. The member nodes are determined by the geo-political hierarchical graph clustering. Insets are shown on a level of detail chosen by the user. For example, an inset can be used to show a whole country as well as a small area. The detail level can be adjusted (see section “Interaction”). The subgraph, consisting of inset’s member (super) nodes and edges, is shown on the top of this map like the graph in the normal view (see Figure 5).

An inset shows potentially distant areas by “moving” them to the current view or it shows enlarged small areas within the current view (see Figures 6(b) and 7(b) and section “On- and off-screen insets”). Within an inset, edges between nodes preserve their relative length. However, edges connecting nodes between an inset and its original location may be distorted and do not carry any information except for connectivity of its adjacent nodes. Although this distance distortion poses a potential limitation, insets aim to provide better graph readability and understandability than the original views. Moreover, we mitigate the influence of distortion on distance readability by additional visual clues (see below).

Figure 6.

On-screen insets: (a) original view and (b) on-screen insets (orange borders) show more details for dense areas. They show zoomed regions of the underlying map.

Figure 7.

Off-screen insets: (a) original view and (b) off-screen insets (black borders) show regions of the graph, which would otherwise lie outside visible screen region.

An inset also shows additional information to the user:

Zoom level. An inset’s zoom level is difficult to judge solely by looking at the inset’s content. This may be the case when the inset shows an area unknown to the user. To provide zoom-level information, we use a progress bar at the bottom of the inset. The minimal value is the scale when the whole world is visible. The maximal value is usually given by the map data provider.

Inset’s displacement. If an inset is not shown on the top of its original geographic position, we indicate the inset’s displacement as a label on the bottom. This is important, as insets should provide the information on the actual distance of their content to the center of the view. We decided to use a label as several alternative visual mappings such as size, color, and progress bars require assumptions about the average and the deviation of distances of nodes in the graph. Moreover, the label provides the exact value which might be a necessary information to the user. We calculate the displacement on the real surface of the earth, not on the view distorted by a transformation such as the spherical Mercator.

Label. Inset’s label indicates the geographic area shown. The name of the area is given by map data providers (if available). Alternatively, it is also possible to use information generated from the results of a clustering or of a data mining algorithm. Examples of labels for algorithm-calculated groupings include the following:

A label text consisting of statistical measures such as mean/median coordinate and size of the area (e.g. “area at 41.9° N, 12.5° E (size: 10 km)”);

Expressions from natural language such as “left area,”“big cluster,” and “small region”;

Cluster numbers such as “Cluster 1”and “Cluster 2”;

Inset type. The border color and drop shadow show the type of inset (on- or off-screen), see below for details.

On- and off-screen insets

We now introduce the two types of insets:

On-screen insets show details of dense areas on the screen;

Off-screen insets show areas outside of the current view.

On-screen insets reduce clutter and off-screen insets minimize the need for panning and zooming.

On-screen insets

On-screen insets are used to show details at dense locations in the view. These small dense areas often suffer from clutter, when exploring the whole graph in one view. They also reduce the need to zoom into these areas, thus loosing the overview of the whole graph. On-screen insets minimize clutter without loosing information about both details of the graph in this area and the overall graph structure. An example graph drawing using on-screen insets is shown in Figure 6(b).

Insets are located on the point of the map, which they show at a larger scale. The insets thus act like a magnifying glass, enabling the user to see the graph at a rough scale while still being able to examine small parts at detailed scale. Unlike fisheye lenses, insets do not distort the map proportions. Since they enlarge a small area, distances inside the inset are approximately proportional to the real distances, which makes them easy to compare.

Off-screen insets

Off-screen insets are an extended version of the insets proposed in Ghani et al.¹ They are used to show distant nodes and their surrounding area located outside the current view. By showing these areas in the current view, the user can examine graph parts in distant areas without the need to navigate to this area on the map. An example graph drawing using off-screen insets is shown in Figure 7(b).

The proposed insets can enhance related approaches mentioned in section “Related work” and reduce clutter. We reduce the number of insets shown using clustering and subgraph visualization. In contrast to Ghani et al.,¹ the probability of edge overplotting decreases when drawing graphs. This is because insets with only one node have the node in their center. If they are placed at the border of the view, being a rectangle, multiple edges are likely to be drawn at the same x- or y-coordinate and thus overlap each other.

Automatic inset-type determination

To determine whether an inset $I$ is an on-screen or off-screen inset, we use a simple intersection test between the area of the inset’s member nodes (i.e. inset’s area $I$ ) and the view $W$ . If $I \cap W = ϕ$ , then the inset will be processed as off-screen inset, else an on-screen inset.

There is also the case when the area of the original positions of the inset’s member nodes and the screen intersect only partially. We decided to use on-screen insets in this case, because off-screen insets might still partially occlude its original area, although giving the impression of showing a distant area. Additionally, a collision detection algorithm (see below) avoids insets being drawn (partially) out of the screen space.

We use both border color and a shadow to distinguish the type of inset. The user should be able to easily distinguish the inset type, as it would lead to false interpretations of edge lengths. Off-screen insets have a black border with an additional drop shadow that points away from screen center, while on-screen insets have an orange border without drop shadow. Note, there are also other ways to visualize the type, such as border style and stroke pattern. Another idea is also to use a different shape for each type. Important is the distinction between them.

Insets’ positions

The position of insets on the screen is very important. It should indicate the true position of the area inside them. Moreover, the insets should not occlude interesting nodes or each other, in order to show the data properly.

We present a special inset positioning approach. The approach consists of two parts: (1) the layout of the content inside the inset and (2) layout of the insets in the whole view.

Content layout

The bounding box of the member node geographic locations (i.e. a “cluster’s” position) determines inset’s content layout. The size of the bounding box defines the inset’s zoom level. The box’s center is used for inset’s positioning. The zoom level is calculated so that the bounding box fits in the rectangular region of the inset. Then the position of the center of the subgraph is moved to the center of the inset. Note, because the content of inset is not continuously changing, it does not suffer from the motion effects as mentioned in Gutwin.¹⁸

Layout of insets on the screen

The insets are positioned according to their type: (1) the layout of on-screen insets depends on the original position of its member nodes, which are shown in detail. This is accomplished by an affine transformation that places the center of the inset in the center of the cluster. (2) For the layout of off-screen insets, we need to find positions that indicate the original positions of their members as well as minimize overplotting.

We propose to use a layout based on an ellipse (see Figure 8(b)). The aim of this layout type is to minimize overplotting of edges, which is often the case in common placements using a rectangle at the border of the screen.¹ Straight line edges are more likely to overplot in a rectangular scheme, because the locations of the insets form a line (see Figure 8(a)).

Figure 8.

Inset positioning example: (a) Positioning on a rectangle and (b) positioning on an ellipse. The inset in yellow has an edge (blue) to every other inset. The red dotted line indicates the placement scheme (rectangle or ellipse). Rectangular positioning leads to edge overlap. Ellipsoid positioning mitigates this problem.

The projection on the ellipse is applied as follows: let $w_{S}$ and $h_{S}$ be the width and the height of the screen, and $w_{I}$ and $h_{I}$ the width and the height of the inset, respectively, then the horizontal axis $a$ and the vertical axis $b$ of the ellipse are calculated as

a = \frac{w_{S}}{2} - \frac{w_{I}}{2}

and

b = \frac{h_{S}}{2} - \frac{h_{I}}{2}

Furthermore, let $α$ be the angle of the original position of the inset’s member nodes as seen from the screen center, then the position $\vec{p}$ of the inset as seen from the screen center is calculated by

α' = {\begin{matrix} \tan^{- 1} (\frac{a}{b} \cdot \tan (α)), & if α is in Quadrant I or IV \\ \tan^{- 1} (\frac{a}{b} \cdot \tan (α)) + π, & if α is in Quadrant II or III \end{matrix}

and

\vec{p} = (\begin{matrix} a \cdot \cos (α') \\ b \cdot \sin (α') \end{matrix})

To avoid numerical problems when $α$ approaches $\pm π / 2$ , we use an equivalent equation, if $| \tan α | \geq | \cot α |$

α' = {\begin{matrix} \cot^{- 1} (\frac{b}{a} \cdot \cot (α)), & if α is in Quadrant I or II \\ \cot^{- 1} (\frac{b}{a} \cdot \cot (α)) + π, & if α is in Quadrant III or IV \end{matrix}

We note that using an ellipse will place insets nearer to the center of the view than a rectangle and thus reducing the usable space there. For small screens, it thus might be better to use a rectangle than an ellipse. We offer this option in our implementation.

Avoiding inset occlusion

Our approach uses collision detection and resolution in order to avoid occlusion and positioning insets partially outside of the visible view. In general, there are three main reasons for inset overlap:

Pairwise occlusion of two insets: two insets on the screen overlap (see the blue rectangle in Figure 9). There are three possibilities for this type of overlap:

Two on-screen insets may overlap, when the areas they show are very close to each other. Due to magnification of the areas, the insets positioned in the center of the areas may occlude.

Two off-screen insets may overlap, when they show areas located in a similar direction from the current view. In this case, insets would be intuitively placed at the same position at the border and thus they would overlap.

An on-screen and an off-screen inset might overlap when the on-screen inset is positioned at the border (or close to it) and an off-screen inset shows an area in the same direction; thus it is located at the same place at the border.

An inset occludes a node (see the green rectangle in Figure 9): An inset may cover a node of the original graph, which is located below the inset.

An inset is positioned on the border of the screen and partially cut-off (see the red rectangles in Figure 9): This can happen when the original area of its nodes is located close to or at the border of the screen, as well as the result of re-arranging overlapping insets.

Figure 9.

Occlusion resolution. Left: original view. Right: after collision resolution. The figure shows three possible types of collisions that can occur when layouting insets. Green rectangle: collision of an inset with nodes (black dots) on the map. Blue rectangles: two overlapping insets. Red rectangle: inset partially cut-off the screen.

Occlusion can be a big disadvantage or even, in worst case, make insets unusable. A deep discussion of occlusion prevention is beyond the scope of this article. However, since it is necessary for insets to work effectively, we implemented a simple but effective algorithm that resolves possible occlusions. An example for an occlusion of insets and its resolution is shown in Figure 9.

Our occlusion avoiding algorithm (see Appendix 1) is inspired by Luboschik et al.³⁷ Our algorithm checks for occlusions and, if an occlusion is detected, it moves the occluded inset (see below) away from the center of occlusion. Since moving an inset might cause new occlusions, the algorithm does not try to resolve all occlusions at once, but works iteratively by moving the inset only a little bit in each step. This way, visualization does not slow down when there are many occlusions. Additionally, updating the visualization iteratively gives in most cases the effect of a smooth movement of the insets and avoids popping effects.

However, in the worst case, the algorithm never finds an occlusion-free solution. This happens, for example, in the most obvious case when there is simply no free space for layouting the insets without causing occlusion. It then tries to converge to a state of equally minimized occlusion of all the affected graph parts.

Our algorithm uses forces to move colliding insets. For each collision, it calculates a force that pushes the inset away from the area of collision (or occlusion). Together with the force, which pushed an inset to its intended location, all forces are finally summarized to a resulting force that is used to move the inset. The algorithm for detecting occlusions as well as the algorithm for calculating the force to resolve an occlusion depends on the type of occlusion.

Pairwise occlusion of two insets. This case is detected using a simple rectangle intersection test for two insets $I_{1}$ and $I_{2}$ : $I_{1} \cap I_{2} \neq ϕ$ . In this case, we calculate the center $C$ of the intersection $X$ and choose the force $F$ so that it points away from it, and its intensity is chosen so that it increases with the amount of the intersection $A_{X}$

\vec{F} = A_{X} \cdot \frac{{\vec{C}}_{I} - {\vec{C}}_{X}}{‖ {\vec{C}}_{I} - {\vec{C}}_{X} ‖}

Since each inset is tested separately with all other insets, both insets will usually detect occlusion and move.

An inset occludes a node. This case is found by checking for intersections of the rectangle of an inset and the nodes. Checking for intersection and calculating the direction of the force work exactly like in the case of two insets. Note that in this case, only the inset is moved, since the node needs to stay at its original location.

An inset is partially out of the screen. An inset $I$ that is partially out of the screen $S$ is found by a rectangle intersection test with the rectangle of the screen bounds: $I \ S \neq ϕ$ . The force is calculated like in the case of an intersection of two insets.

When calculating the resulting force, each force component can be weighted individually, depending on the occluded object. We find the problem of insets being out of screen the most important one, so we assigned these forces a large weight. Compared to that, the force that points to an inset’s intended location has the lowest weight, because we considered occlusion prevention more important than preserving the intended location.

Our algorithm resolves occlusions of insets and nodes. It, however, still may lead to occlusion of edges by insets. This may be resolved by additional edge bundling or edge routing algorithms (see discussion in section “Discussion”). We will tackle this issue in the future. Currently, we rely on the Gestalt law of continuity, where humans are able to perceive an occluded line as one line.³⁸

Inset size

The optimal size of an inset depends on the scale of subgraph, the number of insets, as well as on the interest and intention of the user. The size of new insets is set initially to around 5% of the screen space, so that seven insets (the number of objects that a human can keep simultaneously in working memory³⁹) occupy approximately one-third of the screen. However, we set the lower limit for the side length to 100 pixels preventing from becoming too small. As the initial setting may not be suitable for a dataset at hand, the user can interactively adjust the size of each inset on the screen individually.

Graph-based local distortion

We present an extension of insets specially for drawing graphs. Although on-screen insets can be used to reduce overplotting of nodes and edges in dense areas, these insets cannot resolve the clutter within them (see Figure 11(a)). This is often caused by edge crossing and node overlap within the inset’s area, since the node’s position is fixed to their geographic position.

In case of overlapping and problems with graph structure exploration, we propose to use a graph-based layout of node positions within the inset so that the graph readability improves (see Figure 10). The distortion enhances the graph understanding in small local areas by re-arranging the layout in these areas only. This distortion is performed on user-selected insets.

Figure 10.

Graph-based local distortion: (a) original inset and (b) inset with local distortion of content shows details of the graph structure.

Our local graph-based distortion is based on the following assumption: Although the users are usually interested in the geographic location of a graph, depending on the current zoom level, they may prefer to explore graph structure to the exact location of the nodes. Approximate locations may be sufficient in this case. Figure 1 shows an example. The nodes are located in cities and the edges at global scale represent connections between these cities. The exploration of graph structure in the city may be more important than the exact node positions within them.

To improve the readability of graph structure in an inset, we apply a graph-based layout algorithm to the subgraph of the inset. The user may choose from several layouts such as Kamada–Kawai,⁴⁰ Fruchterman–Reingold,⁴¹ and SpringLayout.⁴² Additionally, the design allows to easily extend this list by any layouting algorithm that works on graphs. The graph-based layout in the insets significantly improves the readability of subgraphs when the geographic location of the nodes in the inset is unbalanced (see Figure 11).

Figure 11.

Inset of the map of O’ahu island: (a) original, (b) graph-based distortion without blurring, and (c) graph-based distortion with blurring.

We would like to note that the graph-based node re-arrangement only approximates node location. This distortion is only within inset’s area, so it is limited to a certain local geographic region. The overall node distribution in the whole graph stays approximately similar.

Enabling local geographic distortion and choosing an algorithm to use for local re-arrangement are tasks that are not as intuitive as panning/zooming, collapsing/expanding nodes, and opening/closing subviews (insets). This will lead to a slight increase in the user’s learning curve. This means that a naive user will probably not be able to use this feature for exploration of a graph efficiently when he is using it for the first time.

The use of graph-based local distortion is optional. Since we do not know whether the user prefers to examine graph structure to real geographic positions, the user can interactively select this option.

Visual clues. For better distinction of the graph-based distortion to normal insets, we included additional visual clues. One clue is the border style. Insets with active distortion are marked by a dashed border in contrast to the solid borders of non-distorted insets. Additionally, we also indicate distortion on the map. This emphasizes the impression that the positions of nodes on this map have been distorted, because showing the graph-based nodes directly on the insets map may lead to improper interpretations of node locations (see Figure 11(b)). The user may interpret the node to be exactly geographically located. Moreover, for islands, the repositioned nodes may appear in the sea, which may not be intuitive in some graphs. For this purpose, we use image effect filters. We experimented with various filters (see section “Discussion”) and a combination of a marble filter (http://www.jhlabs.com/ip/filters/MarbleFilter.html) with a Gaussian filter with kernel size of 17, amount of 1, marbling scale of 6, and turbulence of 0.5 has satisfied our requirement to give the feeling of a diffused image, as well as achieved the following two requirements:

Clue must be strong enough to clearly identify the graph distortion;

Clue must be weak enough to enable recognizing the underlying region as a map.

An example of visual clues employed in graph-based local distortion is shown in Figure 11(c). The image depicts a graph positioned at O’ahu, one of Hawaii’s islands. Our intention was to make the blurring strong enough to distort the map in a recognizable way, that is, the area can still be identified as O’ahu by a user, who would know its rough shape.

We tested different types of map image distortion to mark insets with local distortion enabled. Besides blurring of the map image as used in our examples, we will discuss two other ways:

Figure 12(a) shows an inset where distortion is additionally marked by colorizing the map. This has the advantage to enable the user to easily judge, whether distortion is enabled, even when not looking on the inset directly. However, since color is an important feature to identify the inset’s background as map, the map might become unrecognizable as such.

Figure 12(b) shows an inset using detail and overview to mark the active distortion. This makes it possible to prevent a user from mistaking the nodes’ position as geographically exact, because the background except from the overview area is neutral. Additionally, it shows the overview similar to a thumbnail image in the corner of the inset, including markers for the original node positions. However, it obviously reduces the usable space for the distorted subgraph inside the inset and thus increases clutter. Additionally, it is quite possible that the thumbnail is occluded by the incoming and outgoing edges from and to the inset nodes. Moreover, there is no direct correspondence between the nodes in the inset and in the thumbnail.

Figure 12.

Two additional ways of changing an inset’s background map to indicate distortion (using the example of Figure 16): (a) colorized distorted map for distorted insets and (b) detail and overview for distorted insets.

Interaction

Our approach offers a wide variety of interaction options for exploring the geo-located graphs using insets. As a basis, we provide standard navigation techniques (especially panning and zooming) that are common in interactive map applications (e.g. Google Maps (http://maps.google.de) and Bing Maps (http://www.bing.com/maps)). We enhance them with automatic adjustments of insets. When panning and zooming, the insets are shown/hidden and repositioned automatically to support the user’s current view. Interaction with insets also allows for interactive exploration of the graph hierarchy as insets (video available at http://www.gris.tu-darmstadt.de/research/vissearch/projects/GeoInsets/index.html).

Geographic navigation with the insets:

Zoom-to-location. For a detailed exploration of an area within inset, the user can use the so-called zoom-to-location action. It allows the user to quickly navigate to the location shown inside the inset without manual zooming and panning.

Automatic (dis)appearance of insets. When navigating on the map (zoom and pan), our tool shows/hides insets for better visibility and understandability of the data. For example, when a user zooms in, the on-screen inset’s area may become larger on the underlying map than in the inset. Then the inset will be hidden automatically. Nodes of a hidden inset will be surrounded by a dotted line to indicate that they were part of an inset that has been hidden automatically. If the user pans out of the view of the currently shown graph nodes, the inset for these nodes will reappear. When panning, insets will automatically update their position to prevent displacement. When an on-screen inset gets out of view due to panning or zooming, it will be seamlessly transformed to an off-screen inset. Vice versa, off-screen insets will transform to an on-screen insets when appearing in the view. This transformation is notable by the (dis)appearing displacement indicator, a change in the border color and the (dis)appearing drop shadow that indicates the inset type directly.

Show/hide group of nodes as an inset. The most important way of interacting with an inset for the user is the ability to decide, whether it shall be displayed or not. We thus provide the user the possibility to open/close the inset. For example, the user can transform a (proxy) super node to an inset (open inset). This gives the user the possibility to decide which parts of the graph should be displayed using insets and which not. Note that selecting a node on the screen will create an on-screen inset while selecting a proxy node will create an off-screen inset.

Aggregation hierarchy exploration in insets:

The user can also expand a super node or collapse multiple nodes (see Figure 13). In this way, he can explore the clustering hierarchy, that is, (dis)aggregate nodes. The same is possible for insets (see Figure 15(b) and (c)). The expanding and collapsing nodes/insets allow the user to explore the graph on a more or less detailed level. This operation uses a cluster hierarchy generated by a clustering algorithm (see section “Geo-located hierarchic graph aggregation”).

Figure 13.

User can expand or collapse nodes to explore the graph interactively.

Use cases

We show two applications of our approach using real-world geo-positioned datasets. The first dataset shows a global computer network (video available at http://www.gris.tu-darmstadt.de/research/vissearch/projects/GeoInsets/index.html) and the second one is a graph extracted from a trajectory of a social network user. These use cases are followed by expert feedback and a discussion of our approach.

Computer network

Our first example is a graph representing a part of the global Internet network. The network belongs to the provider Deutsche Telekom. The dataset source is the University of Adelaide’s Topology Zoo website (http://topology-zoo.org/index.html). We want to see the graph structure and its geographic locations in detail and analyze connections between nodes to get a better understanding of the network. This information is useful for maintaining its configuration, for example, when planning new connections where node location (especially country) as well as linkage are the important factors.

The graph has 39 nodes and 62 edges. The nodes are located around the world (see Figure 3(a)). Some nodes are in America and East Asia, but the biggest part is located in Europe. Since Europe is relatively small compared to America and East Asia, the network’s exact structure is hardly visible. The dense structure, especially in Central Europe, makes it difficult to follow the edges. We therefore first aggregate the nodes (see Figure 3(b)). The connections and nodes inside of the countries have been replaced by super nodes to improve the visualization of the overall network. However, Europe has many small countries close together compared to the rest of the world. The view suffers from clutter even when using super nodes. Thus, the structure of the network is not visible everywhere.

To better see the network structure, we use an inset to enlarge Europe (see Figure 6(b)). Now, the overplotting in the dense area has been strongly reduced and the network structure can be easily explored. Insets have advantages in comparison to simple zooming. We can also see where the edges from America and Asia lead to, as the end nodes of the edges are not placed out of the view. Nevertheless, some edges inside the insets are difficult to follow, as they are very short. Therefore, we further improve the view using local distortion.

Figure 10(b) shows the graph using insets with local distortion. The nodes are distributed more evenly, thereby improving graph readability. We chose the Kamada–Kawai algorithm⁴⁰ for positioning the graph within the Europe inset. Then, we adjusted the resulting positions of some nodes with the mouse to further reduce clutter, which could not be resolved by automatic graph layout. As we can see, the readability of the graph structure has significantly improved and there are no more short edges that could be easily overlooked. This minimizes the possibility of misinterpreting the structure by following an edge to the wrong destination. In this view, we now can clearly see that England has a direct connection with America. This was not visible in Figure 10(a), because the edge was occluded by the big edge between Germany and America. Also, France, Switzerland, and Italy are directly connected to the other two countries. Before applying distortion, we could not clearly see these connections, because the three country nodes were plotted in one line and thus the edges occluded each other.

We now further concentrate on Europe by zooming in. Figure 7(a) shows the resulting view with proxy nodes representing countries that are out of the view. They are linked by edges to the nodes in Europe. In order to examine the graph structure within the distant node groups, we use insets (see Figure 7(b)). We can now see the exact locations of the nodes and their country by looking at their location inside the inset. We can also clearly recognize the graph structure within these areas. For example, the big super node in North America belongs to the United States and is connected to Hong Kong and Singapore, but not to Tokyo. This could not be seen before. The use of insets has an additional advantage. Since no permanent interaction is required to see these facts, this view can also be printed out and distributed using traditional media without information loss.

Person’s trajectory

The second example graph is a graph extracted from a trajectory of a user of Brightkite, a location-based social network. The users of Brightkite can store their current location regularly (“checkin”). The data source from the network we used is part of the Stanford Large Network Dataset Collection (http://snap.stanford.edu/data/index.html). We used the chronological list of checkins to build a trajectory graph. We added a node for each checkin at the location of the checkin and connected it to the chronologically previous node by an edge. We selected a user, who uploaded many positions in his, presumably, home area in Oregon and traveled to some distant locations. The user made 704 location checkins, which resulted in a graph of 704 nodes and 703 edges.

The original graph is shown in Figure 14(a). The aggregating nodes to super nodes and aggregating edges solve the problem of overplotting in dense areas, but lead to loss of details (see Figure 14(b)). As we can see, the user made many checkins at locations in a couple of small areas that are very far apart from each other. Note, we used DBSCAN algorithm for clustering, because it can well capture dense areas across region borders.

Figure 14.

Overview of a user’s movement trajectory over 2 years according to the social network Brightkite: (a) original graph and (b) aggregated graph using DBSCAN clustering. The size of super nodes reflects the number of visits in the respective area. Details of aggregated areas are missing.

First, we examine Oregon, the area with the most checkins (see Figure 15(a)). To get more detailed information about the user’s destinations, which are located out of the current view, we use off-screen insets. Figure 15(b) shows the user’s checkins in the distant areas while we still can explore the main part of the trajectory in Oregon. We can see the exact start and end of the edges leading from Oregon to the distant areas. We see which distant nodes are directly connected to Oregon and which are only connected to nodes within the distant area. This view enables us to analyze whether a checkin was part of an excursion or whether the user made a roundtrip in this area, like in the leftmost inset.

Figure 15.

Detailed view on the user’s movement around Oregon (including node and edge aggregation): (a) movements outside the shown area are indicated by the edges pointing out of the visible area, (b) off-screen insets show detailed movement patterns in distant areas, and (c) the magenta dotted inset in (b) has been expanded to three insets showing more details.

We are now interested in more detail of the user’s route, so we expand the insets of interest (see the green rectangle in Figure 15(b)). We decided to expand the leftmost inset (marked using a dotted rectangle) in order to explore the potential roundtrip in this region. After we expand the inset, we can see the details for each of the three regions that had been dense areas in Figure 15(c). Surprisingly, this view reveals that the user must have visited this region twice, because the rightmost of the marked insets shows a node that is not connected to the others, but only to Oregon.

We could continue to explore the graph by expanding the insets in which we are interested in more detail and merging or closing other insets that we consider to be not informative. By doing this, we can see the exact locations the user has visited and can follow his route without loosing track of the rest of the graph. This enables us to discover various data characteristics. For example, whether the user’s trip is a roundtrip or a trip with many excursions, or that unconnected routes that might originate from multiple visits.

If we do not care about the details in the region of Oregon, we can also start exploring the graph by looking at the roughest zoom level. For this, we use on-screen insets as shown in Figure 16(a). The insets are now at the location on the map they represent, being only displaced to avoid occluding each other. We now see details about the route of the user in each area he visited at global scale. Note that in contrast to Figure 15(b), we further expanded super nodes in some insets to demonstrate the effect of locational distortion shown in the following.

Figure 16.

User trajectory at the lowest zoom level to show the whole area the user has visited. (a) On-screen insets show more details in the respective regions. Some of their positions are automatically adapted to avoid overlapping. (b) Local graph-based distortion improves the visibility of detailed structure of the movement.

When looking at Figure 16(a), we see that some insets still have areas where nodes are very close to each other, because we expanded all their super nodes. Using local graph-based distortion, we can resolve this problem and see all the nodes and edges more clearly. Here, we decided to apply distortion to the three leftmost insets, because we think their subgraph is not as clearly visible as the subgraph of the two rightmost insets (see Figure 16(b).)

The edges between nodes in the insets as well as edges connected to nodes outside of an inset can be seen more clearly. This resolves occlusion of short edges by their adjacent nodes. We can see the graph structure inside the insets more clearly. This reduces the probability for mistakes like following the wrong edge when looking at the graph. In the upper right inset of the distorted insets, we can now clearly see that the nodes do not originate from one single visit, but three separate visits. This information could not be clearly seen before, because the two nodes at the coast are very close together making it easy to mistake them as connected (see Figure 16(b)).

Expert feedback

Both types of use cases presented in the previous sections have been evaluated by experts. The following sections present their opinions.

Supply chain network

In the supply-chain management area, the network was composed of factories distributed around a large geographic area. The factories were connected by edges denoting goods transportation. Our new approach allowed the users to examine a production chain of a company.

The experts very much appreciated the possibility to explore the network on several levels of detail simultaneously without the need to zoom and pan to the areas of interest. The experts could analyze the network structure with its geographic location. They especially liked the possibility to explore dense production areas (e.g. industrial agglomerations) within the context of the whole supply-chain network. They would appreciate to extend the approach with additional information on the production chain (e.g. production size, product type).

Trajectory analysis

In trajectory analysis, the new approach extended the state of the art⁴³ and thus allowed efficient exploration of person’s mobility. The whole trajectory includes visits to several continents of the world over a long time period. By combining the overall view on the map and detailed representations in insets, it becomes possible to understand the structure of mobility, identify major transportation hubs used by a person, and understand his travel patterns and interests. The approach provides seamless integration of overview and detail of person’s movement, enabling exploration of local movement in global geographic context. The experts especially liked the flexibility of creating insets and modifying graph layouts; this enables exploration of complex trajectories.

The experts recommend enhancing the technique by visual encoding of various temporal aspects of visits to selected regions represented by insets, namely (1) how often a region has been visited by a person, (2) how long a person stayed in a region, (3) how regular are time intervals between visits, and (4) when visits happen (year, season, month, day of week, time of day). Further enhancements are needed for comparative analysis of multiple trajectories (e.g. different persons, same person during different time intervals).

Discussion

We have shown how our method supports the visualization of geo-located graphs in two different types of scenarios. Additionally, experts praised the method and provided some recommendations to further improve the usability. In this section, we elaborate on three of the most important aspects of our method and discuss their design together with alternatives.

Insets

Insets were shown to be suited well for showing small subgraphs. The user can choose which super nodes should be open in insets for showing details. The maximum number of open insets is only limited by the screen size. Clearly, opening too many insets will occlude the map below the insets, making it difficult to see the insets’ context. To mitigate this problem, the user can reduce insets’ size interactively if she wishes to open more insets or to explore the map.

We provide interactive functions for enabling smooth exploration. For example, an inset is hidden automatically, when the area it shows is in view becomes larger than the zoom inside the inset. This reduces the need for interaction and prevents misinterpretation of the map and graph. A possible drawback of this function could be that layouting results from local distortion need to be disregarded.

Occlusions

Due to their nature, insets occupy screen space in view. They are intended to occupy unused parts of the screen and should not occlude parts of the graph. For this purpose, we presented an occlusion prevention algorithm (see Appendix 1). In addition to resolving occlusion among insets and avoiding insets being partially cut-off the screen, our algorithm also prevents occlusion of parts of the graph. We decided to prevent occlusions with nodes only, because nodes are the most essential parts of a graph. We furthermore decided to not prevent occlusions with edges, because this would significantly reduce the space for placing insets close to their original location. Edge drawing could be improved in various ways as discussed in the following.

Occlusion prevention was not the main focus of this article. So although our occlusion prevention algorithm works well in most cases, it possibly may fail in some extreme situations. One such situation is when the area of all insets exceeds the screen space. We designed the algorithm to keep the occluded areas as small as possible, if it is not possible to resolve them. Our occlusion algorithm works interactively, shown as animation. This allows the user to keep track of the insets’ positions. However, in some cases, this may lead to insets flicking or bouncing. This occurs when the intended locations of multiple insets are very close to each other, but their sizes are comparatively large. Then the forces in the algorithm become large, pushing the insets further than necessary. This then needs to be adapted in the next iteration.

These problems have been mitigated by appropriate setting of the weight of the different forces and the total weight of the resulting force. Moreover, the user can prevent this situation by interactively adjusting the insets’ positions. We plan to improve the algorithm in the future and resolve these remaining issues. Important is to keep the occlusion prevention algorithm running in real-time. It is currently interactive with a runtime of $O (| II | (| II | + | N_{s} |))$ for each iteration. Here, $| II |$ is the number of insets on screen and $| N_{s} |$ is the number of (super) nodes of the graph that are not inside an inset.

Edge drawing

In this article, we concentrate on graphs with geo-positioned nodes. We improve edge readability by local distortion within insets (i.e. on a local scale). On a global scale, further improvements could be introduced. For example, curved edges like Bézier curves,⁴⁴ edge lenses,¹⁷ or edge coloring⁴⁵ could be used. Moreover, if all nodes of group have the same set of neighbors, edges can also be compressed by connecting them to a group box as proposed by Dwyer et al.⁴⁶ Furthermore, this idea can also be applied to insets reducing the amount of global edges.

Conclusion and future work

We have presented a new technique that improves visualization and readability of geo-located graphs visualized on maps. Our approach is based on insets and local area re-arrangements. We use insets for geo-located subgraphs to show details of small dense areas on the screen or to display remote areas located outside of the current view. In this way, the user can examine both global graph structure and details of dense areas as well as of distant areas. In the resulting graphs, the nodes’ locations still represent the geographic information they carry: the insets indicate this information by their relative position on the screen, the map they contain, and the label they show.

Furthermore, we propose to enhance graph structure examination in dense areas by graph-based local position distortion. It positions nodes according to graph structure within small areas, while still retaining approximate node locations on a global scale. Local distortion helps to improve the readability of graph structure inside an inset. We offer the user the possibility to interactively choose the graph layout used for local distortion. We support various interactions with insets. The insets are automatically drawn/hidden and repositioned according to the user’s navigation. The insets forming clusters of graph nodes can be expanded or collapsed on demand. Our method can be applied to graphs that contain geographic information in the nodes. We have shown applications to real computer networks and person’s trajectories. Our approach enables a user to examine a graph that would be difficult to explore using previous approaches.

In the future, we intend to extend our approach in several ways. We would like to incorporate the suggestions made by the experts mentioned in section “Expert feedback.” When the user needs to hover over nodes in order to identify a node of interest, we could introduce interest-based labeling of nodes or a search function for nodes. We currently show inset labels for groups of nodes. The labels for individual nodes are shown only on demand using tooltips as this reduces overplotting caused by labels. We furthermore would like to add automatic support for deciding which areas might require insets, when to use local graph-based distortion, and when to expand or collapse a super node or inset. We next intend to make user studies that help us to find good initial values for user adjustable settings. They will additionally help us to find automated decision methods to support the user during navigation as good as possible. Finally, as this work focuses on static graphs, we aim at presenting an inset-based approach to the challenging visualization of time-dependent geo-located graphs.

Footnotes

Appendix 1 Acknowledgements

We are thankful to our cooperation partners for their insights into supply-chain network structures as well as their helpful feedback on the article and the software.

Funding

This work was partially supported by projects within DFG SPP “Scalable Visual Analytics”. The work was conducted in cooperation with DHL within the project ‘Resilience 360’. The authors are grateful to M. Heiart for his support with the project and with the user feedback.

References

Ghani

Riche

Elmqvist

. Dynamic insets for context-aware graph navigation. Comput Graph Forum 2011; 30(3): 861–870.

Herman

Melançon

Marshall

. Graph visualization and navigation in information visualization: a survey. IEEE T Vis Comput Gr 2000; 6(1): 24–43.

Von Landesberger

Kuijper

Schreck

. Visual analysis of large graphs: state-of-the-art and future research challenges. Comput Graph Forum 2011; 30(6): 1719–1749.

Guo

Chen

MacEachren

. A visualization system for space-time and multivariate patterns (VIS-STAMP). IEEE T Vis Comput Gr 2006; 12(6): 1461–1474.

Guo

. Visual analytics of spatial interaction patterns for pandemic decision support. Int J Geogr Inf Sci 2007; 21(8): 859–877.

Guo

. Flow mapping and multivariate visualization of large spatial interaction data. IEEE T Vis Comput Gr 2009; 15(6): 1041–1048.

Wood

Dykes

Slingsby

. Visualisation of origins, destinations and flows with OD maps. Cartogr J 2010; 47(2): 117–129.

Andrienko

. Spatial generalization and aggregation of massive movement data. IEEE T Vis Comput Gr 2011; 17(2): 205–219.

Nielsen

TAS

Hovgesen

. Urban fields in the making: new evidence from a Danish context. Tijdschr Econ Soc Ge 2005; 96(5): 515–528.

10.

Nielsen

TAS

Hovgesen

. Exploratory mapping of commuter flows in England and Wales. J Transp Geogr 2008; 16(2): 90–99.

11.

Hadlak

Schulz

Schumann

. In situ exploration of large dynamic networks. IEEE T Vis Comput Gr 2011; 17(12): 2334–2343.

12.

Javed

Ghani

Elmqvist

. Polyzoom: multiscale and multifocus exploration in 2d visual spaces. In: Proceedings of the SIGCHI conference on human factors in computing systems, Austin, TX, 5–10 May 2012, pp. 287–296. New York: ACM.

13.

Furnas

. Generalized fisheye views. ACM SIGCHI Bull 1986; 17(4): 16–23.

14.

Furnas

. A fisheye follow-up: further reflections on focus+context. In: Proceedings of the SIGCHI conference on human factors in computing systems, Montréal, QC, Canada, 22–27 April 2006, pp. 999–1008. New York: ACM.

15.

Elmqvist

Henry

Riche

. Melange: space folding for multi-focus interaction. In: Proceedings of the SIGCHI conference on human factors in computing systems, Florence, 5–10 April 2008, pp. 1333–1342. New York: ACM.

16.

Tominski

Gladisch

Kister

. A survey on interactive lenses in visualization. In: EuroVis State-of-the-Art Reports. Eurographics Association, 2014, pp. 43–62, https://dx-doi-org.web.bisu.edu.cn/10.2312/eurovisstar.20141172

17.

Wong

Carpendale

Greenberg

. Edgelens: an interactive method for managing edge congestion in graphs. In: Proceedings of the IEEE symposium on information visualization, 2003, Seattle, WA, 21 October 2003, pp. 51–58. New York: IEEE.

18.

Gutwin

. Improving focus targeting in interactive fisheye views. In: Proceedings of the SIGCHI conference on human factors in computing systems, Minneapolis, MN, 20–25 April 2002, pp. 267–274. New York: ACM.

19.

Hornbæk

Frøkjær

. Reading of electronic documents: the usability of linear, fisheye, and overview+detail interfaces. In: Proceedings of the SIGCHI conference on human factors in computing systems, Seattle, WA, 31 March–5 April 2001, pp. 293–300. New York: ACM.

20.

Shoemaker

Gutwin

. Supporting multi-point interaction in visual workspaces. In: Proceedings of the SIGCHI conference on human factors in computing systems, San Jose, CA, 30 April 2007–3 May, pp. 999–1008. New York: ACM.

21.

Bak

Schaefer

Stoffel

. Density equalizing distortion of large geographic point sets. Cartogr Geogr Inf Sci 2009; 36(3): 237–250.

22.

Sundarararajan

Mengshoel

Selker

. Multi-focus and multi-window techniques for interactive network exploration. In: IS&T/SPIE electronic imaging, Burlingame, CA, 3–7 February 2013, p. 86540O. Bellingham, WA: International Society for Optics and Photonics.

23.

Frisch

Dachselt

. Visualizing offscreen elements of node-link diagrams. Inform Visual. Epub ahead of print 28 January 2013. DOI: 101177/1473871612473589.

24.

Baudisch

Rosenholtz

. Halo: a technique for visualizing off-screen objects. In: Proceedings of the SIGCHI conference on human factors in computing systems, Fort Lauderdale, FL, 5–10 April 2003, pp. 481–488. New York: ACM.

25.

Gustafson

Baudisch

Gutwin

. Wedge: clutter-free visualization of off-screen locations. In: Proceedings of the SIGCHI conference on human factors in computing systems, Florence, 5–10 April 2008, pp. 787–796. New York: ACM.

26.

Thudt

Baur

Carpendale

. Visits: a spatiotemporal visualization of location histories. In: Proceedings of the Eurographics conference on visualization, Leipzig, Germany, 17–21 June 2013, pp. 79–83. Zürich, Switzerland: Eurographics Association.

27.

Furnas

Bederson

. Space-scale diagrams: understanding multiscale interfaces. In: Proceedings of the SIGCHI conference on human factors in computing systems, Denver, CO, 7–11 May 1995, pp. 234–241. New York: ACM Press/Addison-Wesley Publishing Co.

28.

Tominski

Abello

van Ham

. Fisheye tree views and lenses for graph visualization. In: Proceedings of the tenth international conference on IEEE Information visualization, London, 5–7 July 2006, pp. 17–24. New York: IEEE.

29.

Baudisch

Cutrell

Robbins

. Drag-and-pop and drag-and-pick: techniques for accessing remote screen content on touch-and pen-operated systems. In: Proceedings of INTERACT, vol. 3, Zürich, Switzerland, 1–5 September 2003, pp. 57–64. Amsterdam, The Netherlands: IOS Press.

30.

Bezerianos

Balakrishnan

. The vacuum: facilitating the manipulation of distant objects. In: Proceedings of the SIGCHI conference on human factors in computing systems, Portland, OR, 2–7 April 2005, pp. 361–370. New York: ACM.

31.

Moscovich

Chevalier

Henry

. Topology-aware navigation in large networks. In: Proceedings of the SIGCHI conference on human factors in computing systems, Boston, MA, 4–9 April 2009, pp. 2319–2328. New York: ACM.

32.

Madadhain

Fisher

Smyth

. Analysis and visualization of network data using JUNG. J Stat Softw 2005; 10(2): 1–25.

33.

Archambault

Munzner

Auber

. GrouseFlocks: steerable exploration of graph hierarchy space. IEEE T Vis Comput Gr 2008; 14(4): 900–913.

34.

Von Landesberger

Görner

Rehner

. A system for interactive visual analysis of large graphs using motifs in graph editing and aggregation. In: Proceedings of vision modeling visualization workshop, Braunschweig, Germany, 16–18 November 2009, Braunschweig, Germany: TU Braunschweig.

35.

Zinsmaier

Brandes

Deussen

. Interactive level-of-detail rendering of large graphs. IEEE T Vis Comput Gr 2012; 18(12): 2486–2495.

36.

Sander

Ester

Kriegel

. Density-based clustering in spatial databases: the algorithm GDBSCAN and its applications. Data Min Knowl Disc 1998; 2(2): 169–194.

37.

Luboschik

Schumann

Cords

. Particle-based labeling: fast point-feature labeling without obscuring other visual features. IEEE T Vis Comput Gr 2008; 14(6): 1237–1244.

38.

Ware

. Information visualization: perception for design. Amsterdam, The Netherlands: Elsevier, 2013.

39.

Miller

. The magical number seven, plus or minus two: some limits on our capacity for processing information. Psychol Rev 1956; 63(2): 81.

40.

Kamada

Kawai

. An algorithm for drawing general undirected graphs. Inform Process Lett 1989; 31(1): 7–15.

41.

Fruchterman

Reingold

. Graph drawing by force-directed placement. Software Pract Ex 1991; 21(11): 1129–1164.

42.

Eades

. A heuristics for graph drawing. Congr Numer 1984; 42: 146–160.

43.

Andrienko

Bak

. Visual analytics of movement. Berlin, Heidelberg: Springer Publishing Company, Inc., 2013.

44.

Bézier

. How Renault uses numerical control for car body design and tooling. SAE technical paper 680010, 1968.

45.

Jianu

Rusu

Fabian

. A coloring solution to the edge crossing problem. In: Proceedings of the IEEE 13th international conference on information visualisation, Barcelona, 15–17 July 2009, pp. 691–696. New York: IEEE.

46.

Dwyer

Henry Riche

Marriott

. Edge compression techniques for visualization of dense directed graphs. IEEE T Vis Comput Gr 2013; 19(12): 2596–2605.