Geometric Perspectives in Graph Drawing and Information Visualization

Part of CG Week 2017
Brisbane, Tuesday July 4, 2017

Organizers: Steven Chaplick and Kevin Verbeek


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.