GD’18 PhD school

Recent trends in Graph Drawing and Network Visualization
September 24-25, 2018 – Barcelona, Spain

Lecturers

Patrizio Angelini
U. Tübingen, Germany
Patrizio Angelini received his PhD in Computer Science in 2010 from the University of Roma Tre, Italy. After that, he was a Post-doc Fellow at the same University till 2015, when he moved to the University of Tübingen, where he is currently appointed as Research Assistant.
His main interests are in Graph Algorithms, with particular focus on Graph Drawing, Computational Geometry, and Network Visualization. He published over 70 papers in international conferences and journals of the above fields.
David Auber
U. Bordeaux I, France
David Auber is professor at LaBRI (Université de Bordeaux). His main expertise is in information visualization and, more particularly, in visualization of large graphs. He has developed and is in charge of the project Tulip, an information visualization framework dedicated to the analysis and visualization of relational data.
Anna Lubiw
U. of Waterloo, Canada
Anna Lubiw is a professor in the Cheriton School of Computer Science, University of Waterloo, Canada. She has a PhD in computer science from the University of Toronto (1986) and a Masters in combinatorics and optimization from the University of Waterloo (1983).
Her research is in the areas of Graph Drawing, Computational Geometry and Graph Algorithms.
She serves on the editorial boards of the Journal of Graph Algorithms and Applications and the Journal of Computational Geometry.
Hans-Jörg Schulz
Aarhus University, Denmark
Hans-Jörg Schulz received his PhD from the University of Rostock, Germany in 2010 with a thesis on “Explorative Graph Visualization”. He has since worked in the areas of Visual Analytics and Information Visualization, with extended research stays at IBM Research in the US, TU Graz in Austria, and Fraunhofer IGD in Germany. As of May 2018, he is an Associate Professor at Aarhus University in Denmark, where he pursues his current research interest in modular and progressive visualization. In his free time, he is collecting tree visualizations at treevis.net.

Program

Monday, September 24
8:30 – 8:55 Registration
8:55 – 9:00 Welcome
9:00 – 10:45 Anna Lubiw
The Size of Graph Drawings and Representations
10:45 – 11:15 Coffee break
11:15 – 13:00 Hans-Jörg Schulz
Design Considerations for Graph Visualization
13:00 – 14:30 Lunch
14:30 – 15:45 Anna Lubiw
The Size of Graph Drawings and Representations (hands-on session)
15:45 – 16:15 Coffee break
16:15 – 17:30 Hans-Jörg Schulz
Practice Session: The Good, the Bad, the Ugly – Critiquing Graph Visualizations
Tuesday, September 25
9:00 – 10:45 David Auber
Node link diagram of large graphs: bridging the gap between theory and practice
10:45 – 11:15 Coffee break
11:15 – 13:00 Patrizio Angelini
Beyond clustered planarity
13:00 – 14:30 Lunch
14:30 – 15:45 David Auber
Practice Session: Node link diagram on real graphs in practice
15:45 – 16:15 Coffee break
16:15 – 17:30 Patrizio Angelini
Beyond clustered planarity (discussion)

Contents

Patrizio Angelini: Beyond clustered planarity

The standard theoretical model for the representation of graphs that are equipped with a clustering of its vertices is the c-planarity problem, introduced in the 90’s and still widely open. In this model, vertices are points, edges are curves, and clusters are connected regions enclosing all and only the vertices they contain. The goal is to realize a drawing in which unnecessary crossings involving edges or clusters are avoided.

In this lecture I will introduce models for the representation of clustered graphs that are alternative to c-planarity. I will review the literature on these models, focusing in particular on some interesting relationships with other constrained-planarity problems, and discuss related open questions.

The first model is actually a relaxed version of the original one, in which certain types of crossings are allowed, between either pairs of edges, or pairs of clusters, or pairs composed of an edge and a cluster.

The second model, known as hybrid representation, is still using curves to represent edges connecting different clusters, but it employs a different type of representation for the connections inside a cluster. In particular, in the intersection-link model, intra-cluster edges are represented by intersections between geometric objects, while in the NodeTrix model these edges are represented via the corresponding adjacency matrix.

In the afternoon session, I would like to open up an exchange of ideas with the participants about the effectiveness of the presented models.
Also, I would like to set up a brainstorming session, where we can discuss about other possible alternatives for representing the clusters, in order to possibly define new meaningful hybrid models.


David Auber: Node link diagram of large graphs: bridging the gap between theory and practice

Node link diagram are often used to represent graphs. However, visualization of large graphs with such visual metaphor raises many problems due to human perception limits and to the properties of real world graphs. Based on our last decade work, that courses will focus on the way to integrate large scale graph visualization in different application domain.

First one must lay out graphs before start visualization. Force directed algorithms are mostly used for that purpose, we will present an overview of existing methods and discuss on the pro and cons of each method as well as post processing methods to, for instance, consider size of nodes. When working with localised data, most of the time, node positions are fixed. In that case, or when graph layout suffers from too many edge cluttering, edge bundling algorithms may be considered. We will present topological edge bundling techniques as well as image-based ones. Furthermore, when graphs are too large, number of pixels on screen may not be sufficient to reveal information, we will conclude that lecture by theory and practice on multiscale visualisation.

Practice Session: Node link diagram on real graphs in practice

Real world graphs are somewhat all different and all similar. Each time, the algorithms, the techniques and the systems must be tuned to enable to analyze them or to provide meaningful representation of a phenomenon. Choosing the correct layout algorithm, the correct filtering algorithm or the correct post processing algorithm may be difficult since there is a wide range of existing ones.

The purpose of that session will be to manipulate graphs coming from real world application. Each participant will be given a set of graphs and will have to generate a graph visualization by choosing/tuning some existing algorithms. For that purpose, we will use the Tulip software. Tulip enables to use a large range of algorithms including ones provided by the “Open Graph Drawing Framework”. After a rapid introduction to Tulip, participant will be able to write their own python script to generate their own visualization for their graphs. We will then comapre and discuss results obtain by each participant.


Anna Lubiw: The Size of Graph Drawings and Representations

I will begin by reviewing the classic result that every n-vertex planar graph can be drawn with vertices on an n x n grid and with edges as straight line segments. This has two consequences. One is that the n^2 points of the grid act as a universal point set for drawing planar graphs. It is an open question to give tight asymptotic bounds on the size of the smallest universal point set.

Another consequence is that log n bits per coordinate suffice for straight line planar drawings. We will explore other kinds of graph drawings and representations where the vertex coordinates require more bits, and explore the techniques that are used to show such results. For example, we will look at drawings with convex faces, and drawings in constrained regions. We will also look at intersection representations of graphs—for example, representing a graph as intersections of discs may require coordinates of exponentially many bits. Here the approach is to prove that the problem is hard for existential theory of the reals, which is one of the techniques I will discuss.

For the hands-on session we will explore some open questions related to the above. The time is too short for solving problems, but we will discuss how to tackle open questions by formulating doable special cases and by generating new ideas.


Hans-Jörg Schulz: Design Considerations for Graph Visualization

Creating graph visualizations is a multi-faceted endeavor that entails various considerations, including but not limited to choices of data preprocessing, visual encoding, layout generation, color mapping, label placement, and interaction modalities. Among all these choices, there is no inherently “right” or “wrong” way of displaying data – everything goes, as long as it does not misconstrue the underlying data and serves the needs of the analyst. Overlooking and handling this representational flexibility requires additional knowledge, efforts, and skill. Just choosing one among the hundreds of graph visualization techniques available is already a challenge in itself, let alone customizing, parametrizing, and ultimately utilizing it.

This lecture will give a high-level overview of design considerations involved in creating graph visualizations. It will furthermore feature some selected solutions that aid in navigating different options and visualization possibilities by allowing for their interactive adaptation to a visualization scenario at hand. These solutions provide means for tailoring data and view in order to answer questions that are difficult or even impossible to pursue with standard “one size fits all” graph visualization techniques.

Practice Session: The Good, the Bad, the Ugly – Critiquing Graph Visualizations

What makes a good graph visualization? And what a bad one? What are must-haves and no-gos? And how can a good graph visualization be turned into a better one? These questions are tough to answer, as it is hard to formalize what constitutes a “good” graph visualization. A visualization design that may be inappropriate in one scenario may be well suited for another. Developing “an eye” for a visualization design that is functional for a particular scenario and aesthetically pleasing at the same time, often requires years of experience. It is one of those skills that most have established at the end of their PhD, yet that they would have needed at the beginning.

This practice session aims to jumpstart this skill for those new to the field, and to fine-tune it for those who have already some experience in graph visualization. Building on the lecture about design considerations, this joint practical exercise is conceived to put the theoretical background into action by judging and discussing various graph visualization examples. This also includes examples from the participants themselves: All participants are asked to send at least one screenshot/illustration/video of a graph visualization either from their own work or from the literature/web that they want to have jointly discussed to visexamples@treevis.net ahead of the PhD school. We will then go over these examples, training our “eye for visualization design”, and provide the visualization author with ideas for improvements and extensions in the process.