Publications 2018-12-10.

Most of my publications are in theoretical computer science venues, where the author order generally is alphabetical and does not reflect the contributions made by the authors. I have some papers in other venues, where the author order does reflect contributions; those are marked with ◆.

Journals

• Mosaic drawings and cartograms
  R. G. Cano, K. Buchin, T. Castermans, A. Pieterse, W. Sonke, B. Speckmann ◆
  Computer Graphics Forum, 34(3), pp. 361-370, 2015
  (Proc. Eurographics / VGTC Conference on Visualization (EuroVis) 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.

Formally refereed conference proceedings

• Volume-based similarity of linear features on terrains
  W. Sonke, M. van Kreveld, T. Ophelders, B. Speckmann, K. Verbeek ◆
  Proc. 26th ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL), 4 pp., 2018 (to appear)
  Abstract

  Linear features on terrains model the boundaries of ground cover regions, delineate glaciers, or form the boundary of rivers and lakes. When computing the similarity between such linear features, it is important to also take their context into account: the terrain. We hence explore the possibilities of volume-based distance measures for linear features on a terrain. Our measures construct suitable base surfaces between the linear features, which can slice through the input terrain and also hover above. The similarity between two linear features is then captured by the volume of ‘earth’ above the base surface and below the terrain, and possibly also by the volume of ‘air’ below the base surface and above the terrain. We suggest six ways of choosing a suitable base surface. These choices give rise to different measured volumes and will be useful in different applications.

• Optimal algorithms for compact linear layouts
  W. Sonke, K. Verbeek, W. Meulemans, H. M. W. Verbeek, B. Speckmann ◆
  Proc. 11th IEEE Pacific Visualization Symposium (PacificVis), pp. 1-10, 2018
  Abstract

  Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. Common examples of such ordered – and often also directed – graphs are event sequences and processes. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this paper we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn effectively in a specified aspect ratio, while still clearly communicating the linearity of the layout. Our algorithm allows vertices to be drawn as blocks or rectangles of specified sizes to incorporate different drawing styles, label sizes, and even recursive structures. For reasonably-sized drawings the folded layout can be computed interactively. We demonstrate the applicability of our algorithm on graphs that represent process trees, a particular type of process model. Our algorithm arguably produces much more readable layouts than existing methods.

• Computing representative networks for braided rivers
  M. Kleinhans, M. van Kreveld, T. Ophelders, W. Sonke, B. Speckmann, K. Verbeek
  Proc. 33rd International Symposium on Computational Geometry (SoCG), pp. 48:1-48:16, 2017
  Abstract

  Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are $\delta$-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum $\delta$-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.

• Mapping polygons to the grid with small Hausdorff and Fréchet distance
  Q. W. Bouts, I. Kostitsyna, M. van Kreveld, W. Meulemans, W. Sonke, K. Verbeek
  Proc. 24nd European Symposium on Algorithms (ESA), pp. 22:1-22:16, 2016
  Abstract

  We show how to represent a simple polygon $P$ by a grid (pixel-based) polygon $Q$ that is simple and whose Hausdorff or Fréchet distance to $P$ is small. For any simple polygon $P$, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.

Weakly refereed conference proceedings

• A KDS for discrete Morse-Smale complexes
  T. Ophelders, W. Sonke, B. Speckmann, K. Verbeek
  Abstr. Computational Geometry: Young Researchers Forum (CG:YRF), pp. 3:1-3:2, 2018
• Optimal algorithms for compact linear layouts
  W. Meulemans, W. Sonke, B. Speckmann, H. M. W. Verbeek, K. Verbeek
  Abstr. 34th European Workshop on Computational Geometry (EuroCG), pp. 10:1-10:6, 2018
• The hardness of Witness puzzles
  I. Kostitsyna, M. Löffler, M. Sondag, W. Sonke, J. Wulms
  Abstr. 34th European Workshop on Computational Geometry (EuroCG), pp. 67:1-67:6, 2018
• Computing representative networks for braided rivers
  M. Kleinhans, M. van Kreveld, T. Ophelders, W. Sonke, B. Speckmann, K. Verbeek
  Abstr. 33rd European Workshop on Computational Geometry (EuroCG), pp. 45-48, 2017
• Mapping polygons to the grid with small Hausdorff and Fréchet distance
  Q. W. Bouts, I. Kostitsyna, M. van Kreveld, W. Meulemans, W. Sonke, K. Verbeek
  Abstr. 32nd European Workshop on Computational Geometry (EuroCG), pp. 247-250, 2016
• Mosaic drawings and cartograms
  R. G. Cano, K. Buchin, T. Castermans, A. Pieterse, W. Sonke, B. Speckmann
  Abstr. 31st European Workshop on Computational Geometry (EuroCG), pp. 153-156, 2015

Informal publications (arXiv)

• Mapping polygons to the grid with small Hausdorff and Fréchet distance
  Q. W. Bouts, I. Kostitsyna, M. van Kreveld, W. Meulemans, W. Sonke, K. Verbeek
  arXiv:1606.06660

Theses

• Power graph visualizations for event logs
  Willem Sonke
  Master's thesis, TU Eindhoven, 2015
• Reconstructing a level-1-network from quartets
  Willem Sonke
  Bachelor's thesis, TU Eindhoven, 2013

Media

• Ruler of the Plane - games of geometry
  S. Beekhuis, K. Buchin, T. Castermans, T. Hurks, and W. Sonke
  26th International Computational Geometry Multimedia Exposition (CG:MME), 2017
  Available at http://www.win.tue.nl/~kbuchin/proj/ruler/.