PhD school on Recent Trends in GD&NV


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: TBA

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