Geometric Perspectives in Graph Drawing and Information Visualization

Organizers: Steven Chaplick and Kevin Verbeek

Topic

Nowadays we have access to a vast amount of data. However, this opportunity also comes with a lot of challenges, namely that of extracting useful information from this data. An important tool to gain insight into data is information visualization, or, in the specific case of relational data, graph drawing. It is important that these visualizations are available on demand or interactive (that is, efficient) and accurately represent the data (that is, of high quality). Since visualizations are generally 2-dimensional (or, in some cases, 3-dimensional), they are often composed of 2-dimensional shapes (e.g. treemaps, graph drawings, and thematic maps). Therefore, the challenges of creating high-quality visualizations efficiently are inherently geometric, and fit well within the area of computational geometry. In fact, the area of computational geometry offers geometric algorithms with low running times (efficient) and theoretical guarantees on the quality of the output (accurate). Although such algorithms have already seen several applications in the area of graph drawing, where there is some overlap between communities, the transfer of knowledge between the computational geometry community and the visualization community is still very limited. The advanced theoretical techniques developed in the area of computational geometry are often too inaccessible to practitioners in the area of visualization. On the other hand, there is a lack of understanding of the many challenges that visualization researchers face, which include aspects of human cognition and visual design, among others. As a result, many visualization researchers use simple heuristics to compute their visualization, with no guarantees on the quality of the output, whereas there may exist efficient algorithms that can offer those guarantees. The graph drawing community is at the forefront of formalizing this interface between the applied graph visualization community and the computational geometry community. Namely, therein various quality measures (e.g., angular resolution, edge length ratio, etc.) and drawing styles (i.e., where edges are circular arcs, piecewise linear curves) have been studied from the perspective of producing useful visualizations of graphs via efficient algorithms. In particular, the annual Symposium on Graph Drawing and Network Visualization regularly showcases techniques from computational geometry that have been successfully applied to problems in these application areas.

Schedule

• 14:30 - 15:15
  Speaker: Anna Lubiw
  Title: Morphing and Compatible Triangulations of Planar Graph Drawings
  Abstract:
  In morphing, which is a type of reconfiguration problem, we wish to move continuously from one planar drawing of a graph to another, while maintaining planarity. Morphing has applications in animation and in constructing 3-dimensional objects from 2-dimensional slices.
  I will survey results on morphing, including results on morphing with piece-wise linear vertex trajectories. I will also discuss some new work on morphing a planar graph drawing to a convex drawing so that the set of convex angles always improves. To do this we use a new application of Tutte's graph drawing algorithm (appropriate for 2017, the 100th anniversary of Tutte's birth!).
  For many algorithms on planar graphs, a first step is to triangulate the graph. For problems such as morphing where we have two drawings of the graph, a first step is to find 'compatible triangulations' of the two drawings, which necessitates adding new Steiner points, possibly a quadratic number. I will survey work on compatible triangulations, including a new result about hardness of minimizing the number of Steiner points. For the case of morphing, I will describe a way to avoid the quadratic blow-up.
  Throughout, I will mention many open problems.

• 15:15 - 16:00
  Speaker: Giuseppe Liotta
  Title: Graph Drawing Beyond Planarity: Some Results and Open Problems
  Abstract:
  It is well known that drawings of graphs with many edge crossings are hard to read. On the other hand, edge crossings are simply unavoidable when the graph to be drawn is not planar. As a consequence a number of relaxations of the notion of graph planarity relaxation have been proposed in the literature. They allow edge crossings but forbid specific configurations which would affect the readability of the graph representation. For each such relaxation, different research questions can be asked having both algorithmic and combinatorial nature. Aim of the talk is to briefly survey the rapidly growing research area about graph drawing beyond planarity, pointing out some of its most investigated questions and some of the most prominent open questions.

• 16:00 - 16:30
  Coffee break

• 16:30 - 17:15
  Speaker: Bettina Speckmann
  Title: Geometric Algorithms for Information Visualization
  Abstract:
  The fields of Information Visualization and Visual Analytics develop computer-supported, interactive, visual representations which allow users to extract meaning from large and heterogeneous data sets. Geo-visualization is concerned specifically with the visualization and exploration of geographic data, often in terms of (thematic) maps. Many (geo-)visualization questions give rise to interesting geometric problems which can be solved with techniques from computational geometry. In this talk I will review some recent results from the Applied Geometric Algorithms group in Eindhoven, with a focus on geometric algorithms for geo-visualization.

• 17:15 - 18:00
  Speaker: Tim Dwyer
  Title: Visualising Relational Data in a Geographic Context
  Abstract:
  I will review recent work at the Monash Adaptive Visualisation Lab that seeks to find effective ways to visualise complex relational data in the context of a map. This work bridges computational geometry and graph drawing, the geographic context being a geometry that has to be respected, at least in some respects, while still seeking to find ways to untangle the network connectivity as much as possible. The challenges are not just algorithmic. Much of our work is in seeking creative design solutions to the problems, to avoid the computational challenges wherever possible. Still, inevitably algorithmic (and especially optimisation) challenges arise and are essential to high-quality visual representations of such complex data. We will consider visualisation of flows on maps, visualising dissimilarity on maps, and some recent work on novel world map projections in VR.