Research

Journal Articles
Strongly Refereed Conference Proceedings
Weakly Refereed Conference Proceedings

Journal Articles

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) is a support of a hypergraph H = (V,S) if every hyperedge induces a connected subgraph in G. Supports are used for certain types of hypergraph visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying 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 V. We first show, from a theoretical point of view, that the problem is NP-hard already under rather mild conditions as well as a negative approximability results. 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. Further, we evaluate the performance and trade-offs between solution quality and speed of several 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

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.
－ 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 ]
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 ]

Strongly Refereed Conference Proceedings

A Practical Algorithm for Spatial Agglomerative Clustering
Thom Castermans, Bettina Speckmann, and Kevin Verbeek.
Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, pp. 174—185, 2019.

－ Abstract

 We study an agglomerative clustering problem motivated by visualizing disjoint glyphs (represented by geometric shapes) centered at specific locations on a geographic map. As we zoom out, the glyphs grow and start to overlap. We replace overlapping glyphs by one larger merged glyph to maintain disjointness. Our goal is to compute the resulting hierarchical clustering efficiently in practice. A straightforward algorithm for such spatial agglomerative clustering runs in On 2 log n time, where n is the number of glyphs. This is not efficient enough for many real-world datasets which contain up to tens or hundreds of thousands of glyphs. Recently the theoretical upper bound was improved to Onα(n) log 7 n time [10], where α(n) is the extremely slow growing inverse Ackermann function. Although this new algorithm is asymptotically much faster than the naive algorithm, from a practical point of view, it does not perform better for n ≤ 10 6 . In this paper we present a new agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice. 
－ BibTeX
```
@article{a-practical-algorithm-for-spatial-agglomerative-clustering:2019,
 title = {A Practical Algorithm for Spatial Agglomerative Clustering},
 author = {Thom Castermans and Bettina Speckmann and Kevin Verbeek},
 year = {2019},
 bookTitle = {Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments},
}
```
[ PDF ]
A Philosophical Perspective on Visualization for Digital Humanities
Hein van den Berg, Arianna Betti, Thom Castermans, Rob Koopman, Bettina Speckmann, Kevin Verbeek, Titia van der Werf, Shenghui Wang, and Michel A. Westenberg.
Proc. 3rd Workshop on Visualization for the Digital Humanities (VIS4DH), 2018.

－ Abstract

In this position paper, we describe a number of methodological and philosophical challenges that arose within our interdisciplinary Digital Humanities project \catvis, which is a collaboration between applied geometric algorithms and visualization researchers, data scientists working at OCLC, and philosophers who have a strong interest in the methodological foundations of visualization research. The challenges we describe concern aspects of one single epistemic need: that of methodologically securing (an increase in) trust in visualizations. We discuss the lack of ground truths in the (digital) humanities and argue that trust in visualizations requires that we evaluate visualizations on the basis of ground truths that humanities scholars themselves create. We further argue that trust in visualizations requires that a visualization provides provable guarantees on the faithfulness of the visual representation and that we must clearly communicate to the users which part of the visualization can be trusted and how much. Finally, we discuss transparency and accessibility in visualization research and provide measures for securing transparency and accessibility.
－ BibTeX
```
@article{a-philosophical-perspective-on-visualization-for-digital-humanities:2018,
    title = {A Philosophical Perspective on Visualization for Digital Humanities},
    author = {Hein van den Berg and Arianna Betti and Thom Castermans and Rob Koopman and Bettina Speckmann and Kevin Verbeek and Titia van der Werf and Shenghui Wang and Michel A. Westenberg},
    year = {2018},
    bookTitle = {Proc. 3rd Workshop on Visualization for the Digital Humanities (VIS4DH)},
}
```
[ PDF ]
Agglomerative Clustering of Growing Squares
Thom Castermans, Bettina Speckmann, Frank Staals, and Kevin Verbeek.
13th Latin American Theoretical INformatics Symposium (LATIN), pp. 260—274, 2018.

－ Abstract

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n(log n log log n)2) space, supports queries in worst case O(log3 n) time, and updates in O(log7 n) amortized time. This leads to an O(n α(n) log7 n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n2 log n) time algorithm.
－ BibTeX
```
@article{agglomerative-clustering-of-growing-squares:2018,
 title = {Agglomerative Clustering of Growing Squares},
 author = {Thom Castermans and Bettina Speckmann and Frank Staals and Kevin Verbeek},
 year = {2018},
 bookTitle = {13th Latin American Theoretical INformatics Symposium (LATIN)},
}
```
[ PDF ]
BolVis: Visualization for Text-Based Research in Philosophy
Pauline van Wierst, Steven Hofstede, Yvette Oortwijn, T.H.A. Castermans, Rob Koopman, Shenghui Wang, Michel A. Westenberg, and Arianna Betti.
Proc. 3rd Workshop on Visualization for the Digital Humanities (VIS4DH), 2018.

－ Abstract

Traditional research in philosophy consists for a large part in conceptual analysis and close reading of texts. This is a precise but time-consuming approach, in which the researcher focuses on one particular text passage or one philosophical concept from one or more works of an author. In this paper, we present BolVis, a visualization tool for text-based research in philosophy. BolVis allows researchers to determine quickly which parts of a text corpus are most relevant for their research by performing a semantic similarity search on words, sentences, and passages. It supports activities such as filtering, exploring the semantic context, comparing, performing close reading on selected passages, et cetera. Our approach enables in-depth analysis of texts at a significantly greater scale than is possible by traditional means, thereby allowing researchers to gain in speed without compromising on precision. We demonstrate the usefulness of BolVis by applying it to a corpus consisting of about 11,000 pages of the writings of the Bohemian polymath Bernard Bolzano (1781--1848). Our use case addresses an open question about Bolzano's ideas concerning size equality for sets of natural numbers, and we show that the use of BolVis enabled us to find (at least a significant part of) the reason why he came to accept one-to-one correspondence as a sufficient criterion for size equality.
－ BibTeX
```
@article{bolvis-visualization-for-text-based-research-in-philosophy:2018,
    title = {BolVis: Visualization for Text-Based Research in Philosophy},
    author = {Pauline van Wierst and Steven Hofstede and Yvette Oortwijn and T.H.A. Castermans and Rob Koopman and Shenghui Wang and Michel A. Westenberg and Arianna Betti},
    year = {2018},
    bookTitle = {Proc. 3rd Workshop on Visualization for the Digital Humanities (VIS4DH)},
}
```
[ PDF ]
Competitive Searching for a Line on a Line Arrangement
Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans.
29th International Symposium on Algorithms and Computation, ISAAC 2018, 2018.

－ Abstract

We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher S, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where S has all knowledge. In the case where S knows all lines but not which one is sought, the strategy is 79-competitive. We also show that it may be necessary to travel on Ω(n) lines to realize a constant competitive ratio. In the case where initially, S does not know any line, but learns about the ones it encounters during the search, we give a 414.2-competitive search strategy.
－ BibTeX
```
@article{competitive-searching-for-a-line-on-a-line-arrangement:2018,
 title = {Competitive Searching for a Line on a Line Arrangement},
 author = {Quirijn Bouts and Thom Castermans and Arthur van Goethem and Marc van Kreveld and Wouter Meulemans},
 year = {2018},
 bookTitle = {29th International Symposium on Algorithms and Computation, ISAAC 2018},
}
```
[ PDF ]
Short Plane Supports for Spatial Hypergraphs
Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan.
Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings, pp. 53—66, 2018.

－ Abstract

A graph G = (V,E) is a support of a hypergraph H = (V,S) if every hyperedge induces a connected subgraph in G. Supports are used for certain types of hypergraph visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying 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 V. We first show, from a theoretical point of view, that the problem is NP-hard already under rather mild conditions as well as a negative approximability results. 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. Further, we evaluate the performance and trade-offs between solution quality and speed of several heuristics relative to each other and compared to optimal solutions.
－ BibTeX
```
@article{short-plane-supports-for-spatial-hypergraphs:2018,
 title = {Short Plane Supports for Spatial Hypergraphs},
 author = {Thom Castermans and Mereke van Garderen and Wouter Meulemans and Martin Nöllenburg and Xiaoru Yuan},
 year = {2018},
 bookTitle = {Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings},
}
```
[ PDF ]
GlottoVis: Visualizing Language Endangerment and Documentation
T.H.A. Castermans, B. Speckmann, K.A.B. Verbeek, M.A. Westenberg, and H. Hammarström.
Proc. 2nd Workshop on Visualization for the Digital Humanities (VIS4DH), pp. 1—5, 2017.

－ Abstract

We present GlottoVis, a system designed to visualize language endangerment as collected by UNESCO and descriptive status as collected by the Glottolog project. Glottolog records bibliographic data for the world’s (lesser known) languages. Languages are documented with increasing detail, but the number of native speakers of minority languages dwindles as their population shifts to other more dominant languages. Hence one needs to visualize documentation level and endangerment status at the same time, to browse for the most urgent cases (little documentation and high endangerment) and to direct funding aimed at describing endangered languages. GlottoVis visualizes these two properties of languages and provides an interface to search and filter. Our tool is web-based and is comprised of glyphs on a zoomable geographic map. Clustering and (visual) data aggregation are performed at each zoom level to avoid overlap of glyphs. This reduces clutter and improves readability of the visualization. Preliminary tests with expert users confirm that our tool supports their desired workflow well.
－ BibTeX
```
@article{glottovis-visualizing-language-endangerment-and-documentation:2017,
    title = {GlottoVis: Visualizing Language Endangerment and Documentation},
    author = {T.H.A. Castermans and B. Speckmann and K.A.B. Verbeek and M.A. Westenberg and H. Hammarström},
    year = {2017},
    bookTitle = {Proc. 2nd Workshop on Visualization for the Digital Humanities (VIS4DH)},
}
```
[ PDF ]
Ruler of the Plane - Games of Geometry
S. Beekhuis, K. Buchin, T. Castermans, T. Hurks, and W. Sonke.
33rd International Symposium on Computational Geometry (SoCG), pp. 631—635, 2017.

－ Abstract

Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.
－ BibTeX
```
@article{ruler-of-the-plane-games-of-geometry:2017,
 title = {Ruler of the Plane - Games of Geometry},
 author = {S. Beekhuis and K. Buchin and T. Castermans and T. Hurks and W. Sonke},
 year = {2017},
 bookTitle = {33rd International Symposium on Computational Geometry (SoCG)},
}
```
[ PDF ]
GlamMap: Geovisualization for e-Humanities
T.H.A. Castermans, B. Speckmann, K.A.B. Verbeek, M.A. Westenberg, A. Betti, and H. van den Berg.
Proc. 1st Workshop on Visualization for the Digital Humanities (VIS4DH), pp. 1—5, 2016.

－ Abstract

This paper presents GlamMap, a visualization tool for large, multi-variate georeferenced humanities data sets. Our approach visualizes the data as glyphs on a zoomable geographic map, and performs clustering and data aggregation at each zoom level to avoid clutter and to prevent overlap of symbols. GlamMap was developed for the Galleries, Libraries, Archives, and Museums (GLAM) domain in cooperation with researchers in philosophy. We demonstrate the usefulness of our approach by a case study on history of logic, which involves navigation and exploration of 7100 bibliographic records, and scalability on a data set of sixty million book records.
－ BibTeX
```
@article{glammap-geovisualization-for-e-humanities:2016,
    title = {GlamMap: Geovisualization for e-Humanities},
    author = {T.H.A. Castermans and B. Speckmann and K.A.B. Verbeek and M.A. Westenberg and A. Betti and H. van den Berg},
    year = {2016},
    bookTitle = {Proc. 1st Workshop on Visualization for the Digital Humanities (VIS4DH)},
}
```
[ PDF ]
GlamMapping Trove
A. Betti, T.H.A. Castermans, B. Speckmann, H. van den Berg, and K.A.B. Verbeek.
Proc. VALA, 2016.

－ Abstract

This paper presents the current state of development of GlamMap, a visualisation tool that displays library metadata on an interactive, computer-generated geographic map. The focus in the paper is on the most crucial improvement achieved in the development of the tool: GlamMapping Trove. The visualisation of Trove’s sixty-million book records is possible thanks to an improved database structure, more efficient data retrieval, and more scalable visualisation algorithms. The paper analyses problems encountered in visualising massive datasets, describes remaining challenges for the tool, and presents a use case demonstrating GlamMap’s ability to serve researchers in the history of ideas.
－ BibTeX
```
@article{glammapping-trove:2016,
    title = {GlamMapping Trove},
    author = {A. Betti and T.H.A. Castermans and B. Speckmann and H. van den Berg and K.A.B. Verbeek},
    year = {2016},
    bookTitle = {Proc. VALA},
}
```
[ PDF ]

Weakly Refereed Conference Proceedings

Agglomerative Clustering of Growing Squares
Thom Castermans, Bettina Speckmann, Frank Staals, and Kevin Verbeek.
pp. 8:1—8:6, 2018.

－ BibTeX

@article{agglomerative-clustering-of-growing-squares:2018,
    title = {Agglomerative Clustering of Growing Squares},
    author = {Thom Castermans and Bettina Speckmann and Frank Staals and Kevin Verbeek},
    year = {2018},
    bookTitle = {},
}

[ PDF ]

Short Plane Support Trees for Hypergraphs
Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan.
pp. 35:1—35:6, 2018.

－ Abstract

In many domains, the aggregation or classification of data elements leads to various intersecting sets. To allow for intuitive exploration and analysis of such data, set visualization aims to represent the elements and sets graphically. In more theoretical literature, such set systems are often referred to as hypergraphs. A support graph is a notion for drawing such a hypergraph, understood as a regular graph spanning the same vertices (elements), in which each hyperedge (set) induces a connected subgraph. In this paper, we investigate finding a support graph of a hypergraph with fixed vertex locations under various constraints. We focus on enforcing planarity using a straight-line embedding, while minimizing the total length of the edges of the support graph, and consider the effect of the additional requirement that the support graph is acyclic.
－ BibTeX
```
@article{short-plane-support-trees-for-hypergraphs:2018,
 title = {Short Plane Support Trees for Hypergraphs},
 author = {Thom Castermans and Mereke van Garderen and Wouter Meulemans and Martin Nöllenburg and Xiaoru Yuan},
 year = {2018},
 bookTitle = {},
}
```
[ PDF ]
Mosaic Drawings and Cartograms
R.G. Cano, K.A. Buchin, T.H.A. Castermans, A. Pieterse, W.M. Sonke, and B. Speckmann.
pp. 153—156, 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.A. Buchin and T.H.A. Castermans and A. Pieterse and W.M. Sonke and B. Speckmann},
    year = {2015},
    bookTitle = {},
}
```
[ PDF ]

Theses

Algorithms for Visualization in Digital Humanities
Thomas Hubertus Alphonsus Castermans.
2019.

－ BibTeX

@article{algorithms-for-visualization-in-digital-humanities:2019,
    title = {Algorithms for Visualization in Digital Humanities},
    author = {Thomas Hubertus Alphonsus Castermans},
    year = {2019},
    bookTitle = {},
}

[ PDF ]