promotor: prof.dr. B. Speckmann (TU/e)
copromotor: dr. K.A.B. Verbeek (TU/e)
Technische Universiteit Eindhoven
Date: 30 November 2017
A graph is the mathematical abstraction of a network. It consists of vertices and edges connecting those vertices. A geographic graph is a graph where vertices are associated with locations. An example of a geographic graph is one modelling a road network: the vertices correspond to intersections and the edges to the roads connecting them. In this thesis we consider several questions regarding the construction and visualization of such geographic graphs.
Constructing Geographic Graphs
In the first part of this thesis we consider the efficient construction of geographic graphs. That is, we consider the task of computing a set of edges to connect a given set of points. In particular, we propose new algorithms for the computation of the greedy spanner on a set of points. The greedy spanner is a specific graph resulting from repeatedly adding an edge connecting the closest pair of points that fit a specific condition.
The greedy spanner has proven to have many good properties when used in the context of geographic graph construction. It can connect vertices using very few edges while guaranteeing that, between any pair of points, the shortest distance along the graph is small compared to the geometric distance between those points. However, existing algorithms to compute the greedy spanners are expensive in terms of computation time as well as memory requirements.
By using the well-separated pair decomposition as the underlying structure for our proposed algorithm, we significantly decrease the memory requirements of the computation. Furthermore, we identified a specific structure among greedy spanners computed on different point sets. We used this structure to formulate a geometric property that can be checked locally and quickly for each point. Using this property we can exclude the existence of large groups of potential edges connecting to that point in the greedy spanner. As such, we can avoid most of the expensive computations needed to search for these edges, leading to a big improvement of the running time of our algorithm.
Visualizing Geographic Graphs
Computers can perform a wide range of computations at amazing speeds, however, for many decisions the insights of a human are still required. To make informed decisions about geographic graphs it is important to understand their structure. A good visualization can prove to be invaluable in conveying the properties and structure of these graphs to the user.
When dealing with geographic graphs, vertices often have predefined positions and a geographic context. Hence we explore graph representations on or as maps. We pursue two different types of visualizations, targeting two categories of geographic graphs. For vertex-weighted geographic graphs we consider area cartograms and for edge-weighted cartograms we designed a system for visualizing them as linear cartograms.
Area cartograms are a type of thematic map where the regions of the map are scaled such that their areas correspond to the underlying data. In the context of vertex-weighted graphs, the vertices are encoded as regions and their edges as adjacencies between those regions: the cartogram is a contact representation of the graph. We consider a specific type of area cartogram: mosaic cartograms. Mosaic cartograms represent their regions using a mosaic drawing. In a mosaic drawing, vertices are represented by connected sets of tiles called configurations. One of the advantages of using this drawing style to create a cartogram is that it makes the areas of configurations countable, and as such allows the user to quickly and accurately determine the associated values.
We first consider a complexity measure for mosaic drawings of unweighted graphs, i.e. drawings where there are no requirements on the number of tiles in each configuration. This measure expresses the complexity of a drawing in terms of its complement. We find that less complex drawings need more tiles to encode the correct graph. As such, we investigate the trade-off between small, complex drawings and big well-structured drawings.
Next, we consider the problem of creating mosaic drawings whose shape is similar to a given input shape. In area cartograms it is important that the regions are easy to identify. By using configurations which are similar to the geographic regions which they represent, a mosaic cartogram can convey the structure of its underlying graph at a glance. Using the region outline as the input for our algorithms, we compute a configuration which is similar to the input with respect to specific similarity measures. We investigate two of these measures: the Hausdorff distance and the Fréchet distance. We prove that minimizing the Hausdorff distance is NP-hard and propose an algorithm that computes a configuration with low Hausdorff distance to the input. We show that not all inputs admit a configuration with low Fréchet distance and propose a fatness condition on the input.
Finally, we propose an algorithm which computes configurations whose Fréchet distance is constant with respect to the fatness of the input.
To visualize edge-weighted geographic graphs we considerer linear cartograms. Whereas area cartograms scale regions to encode vertex weights, linear cartograms deform the map such that the distance between locations corresponds to edge weights. We propose an algorithm that deforms a mesh using constraint multi-dimensional scaling (MDS). Using hardware accelerated texture mapping the map is drawn onto the mesh. In contrast to normal MDS our constraint version ensures that the topology of the mesh, and hence the deformed map, is preserved.
We created a system to demonstrate and evaluate our algorithm in practice. By using sparse matrix computation for our MDS we achieve interactive speeds, allowing the system to respond directly to user input. This makes it possible for the user to adjust weights on the fly while analyzing multivariate input data. As complex weighted graphs can not be encoded in the two dimensions of our deformed map, we augment our visualization using several overlays. We introduce glyphs to show any remaining errors as well as a reference grid and displacement vectors which both help to preserve the mental map, as our algorithm deforms the geography.
We conclude with an experimental evaluation where we use our system to analyze complex real-world multivariate data (socioeconomic data from the UK) and to convey the structure of a dynamic weighted geographic network (a power-grid in Australia).