Short Plane Supports for Spatial Hypergraphs
Thom H.A. Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan.
Journal of Graph Algorithms and Applications,
23(3):463—498,
2019.
－ Abstract
A graph G=(V,E)G=(V,E) is a support of a hypergraph H=(V,S)H=(V,S) if every hyperedge induces a connected subgraph in GG. Supports are used for certain types of hypergraph drawings, also known as set visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This scenario appears when, e.g., modeling set systems of geospatial locations as hypergraphs. Following established aesthetic quality criteria, we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set VV. From a theoretical point of view, we first show that the problem is NP-hard already under rather mild conditions, and additionally provide a negative approximability result. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Furthermore, we evaluate the performance and trade-offs between solution quality and speed of heuristics relative to each other and compared to optimal solutions.
－ BibTeX
@article{short-plane-supports-for-spatial-hypergraphs:2019,
title = {Short Plane Supports for Spatial Hypergraphs},
author = {Thom H.A. Castermans and Mereke van Garderen and Wouter Meulemans and Martin Nöllenburg and Xiaoru Yuan},
year = {2019},
bookTitle = {Journal of Graph Algorithms and Applications},
}
[ PDF ]
SolarView
Thom Castermans, Kevin Verbeek, Bettina Speckmann, Michel A. Westenberg, Rob Koopman, Shenghui Wang, Hein van den Berg, and Arianna Betti.
IEEE Transactions on Visualization and Computer Graphics,
25(10):2969—2982,
2019.
－ Abstract
<p>We propose a novel type of low distortion radial embedding which focuses on one specific entity and its closest neighbors. Our embedding preserves near-exact distances to the focus entity and aims to minimize distortion between the other entities. We present an interactive exploration tool SolarView which places the focus entity at the center of a "solar system" and embeds its neighbors guided by concentric circles. SolarView provides an implementation of our novel embedding and several state-of-the-art dimensionality reduction and embedding techniques, which we adapted to our setting in various ways. We experimentally evaluated our embedding and compared it to these state-of-the-art techniques. The results show that our embedding competes with these techniques and achieves low distortion in practice. Our method performs particularly well when the visualization, and hence the embedding, adheres to the solar system design principle of our application. Nonetheless - as with all dimensionality reduction techniques - the distortion may be high. We leverage interaction techniques to give clear visual cues that allow users to accurately judge distortion. We illustrate the use of SolarView by exploring the high-dimensional metric space of bibliographic entity similarities.</p>
－ BibTeX
@article{solarview:2019,
title = {SolarView},
author = {Thom Castermans and Kevin Verbeek and Bettina Speckmann and Michel A. Westenberg and Rob Koopman and Shenghui Wang and Hein van den Berg and Arianna Betti},
year = {2019},
bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
}
[ PDF ]
[ PDF ]
Simultaneous Visualization of Language Endangerment and Language Description
Harald Hammarström, T.H.A. Castermans, Robert Forkel, Kevin Verbeek, Michel A. Westenberg, and Bettina Speckmann.
Language Documentation & Conservation,
12:359—392,
2018.
－ Abstract
The world harbors a diversity of some 6,500 mutually unintelligible languages. As has been increasingly observed by linguists, many minority languages are becoming endangered and will be lost forever if not documented. Urgently indeed, many efforts are being launched to document and describe languages. This undertaking naturally has the priority toward the most endangered and least described languages. For the first time, we combine world-wide databases on language description (Glottolog) and language endangerment (ElCat, Ethnologue, UNESCO) and provide two online interfaces, GlottoScope and GlottoVis, to visualize these together. The interfaces are capable of browsing, filtering, zooming, basic statistics, and different ways of combining the two measures on a world map background. GlottoVis provides advanced techniques for combining cluttered dots on a map. With the tools and databases described we seek to increase the overall knowledge of the actual state language endangerment and description worldwide.
－ BibTeX
@article{simultaneous-visualization-of-language-endangerment-and-language-description:2018,
title = {Simultaneous Visualization of Language Endangerment and Language Description},
author = {Harald Hammarström and T.H.A. Castermans and Robert Forkel and Kevin Verbeek and Michel A. Westenberg and Bettina Speckmann},
year = {2018},
bookTitle = {Language Documentation & Conservation},
}
[ PDF ]
Mosaic Drawings and Cartograms
R.G. Cano, K. Buchin, T.H.A. Castermans, A. Pieterse, W.M. Sonke, and B. Speckmann.
Computer Graphics Forum,
34(3):361—370,
2015.
－ Abstract
Cartograms visualize quantitative data about a set of regions such as countries or states. There are several different types of cartograms and – for some – algorithms to automatically construct them exist. We focus on mosaic cartograms: cartograms that use multiples of simple tiles – usually squares or hexagons – to represent regions. Mosaic cartograms communicate well data that consist of, or can be cast into, small integer units (for example, electorial college votes). In addition, they allow users to accurately compare regions and can often maintain a (schematized) version of the input regions’ shapes. We propose the first fully automated method to construct mosaic cartograms. To do so, we first introduce mosaic drawings of triangulated planar graphs. We then show how to modify mosaic drawings into mosaic cartograms with low cartographic error while maintaining correct adjacencies between regions. We validate our approach experimentally and compare to other cartogram methods.
－ BibTeX
@article{mosaic-drawings-and-cartograms:2015,
title = {Mosaic Drawings and Cartograms},
author = {R.G. Cano and K. Buchin and T.H.A. Castermans and A. Pieterse and W.M. Sonke and B. Speckmann},
year = {2015},
bookTitle = {Computer Graphics Forum},
}
[ PDF ]
[ PDF ]