Invited Speakers
Good drawings and rotation systems of complete graphs (slides)
Oswin Aichholzer (University of Technology Graz, Austria)
In a good drawing of a complete graph the vertices are drawn as distinct points in the plane, edges are drawn as non-self-intersecting continuous arcs connecting its two end points, but not passing through any other point representing a vertex. Moreover, any pair of edges intersects at most once, either in their interior or at a common endpoint, no tangencies are allowed and no three edges pass through a single crossing. These drawings are also called simple topological graphs.
A rotation system (of a good drawing of a complete graph) gives, for each vertex v of the graph, the circular ordering around v of all edges incident to v. In combinatorial mathematics, rotation systems were first used by Hefner in 1891 to encode embeddings of graphs onto orientable surfaces, determining its genus. In the plane (or equivalently on the sphere) the rotation system of a good drawing does not fully determine the drawing, but contains combinatorial information like all pairs of edges which intersect.
We present basic properties of these two concepts, as well as recent progress. This includes results on the number of realizable rotation systems, the crossing number of complete graphs (including the recent concept of shellability of a good drawing), relations to other systems like the order type of a point set, etc.
Biography
The research area of Oswin Aichholzer is Discrete and Computational Geometry with a focus on geometric graphs, that is, graphs where vertices are points in the plane and edges are straight lines. Beside general combinatorial and algorithmic questions in this area he is especially interested in the rectilinear crossing number of complete graphs. Since a few years he also works on the crossing number of good drawings, and in his talk he will point out relations between the geometric and the topological setting and present results obtained from this interplay.
Matrix-Based Visualization of Graphs (slides)
Jean-Daniel Fekete (INRIA, France)
For decades, graph drawing has focused on the node-link representation, trying to address multiple important, difficult, and interesting issues related to 2D embeddings under some optimality criteria (planar drawing, minimizing crossings, optimizations, graph decompositions, and many more). Visualizing a graph structure using its adjancency matrix is much less common, although it has been shown to be more efficient than the node-link representation when the graph becomes dense, for important low-level tasks. The main question to address in matrix-based visualization is the computation of the vertices order. This problem is known with multiple names: linear ordering, seriation, reordering. With a proper ordering, a visualized matrix reveals important patterns and structures of the graph. We will briefly explain how the problem has been formalized in the past, some visual results sometimes revealing unexpected information. We then list some challenges to the community that could be used to motivate the graph drawing community to study the problem, and provide useful solutions for people who need to make sense of complex graphs.
Biography
Jean-Daniel Fekete is Senior Research Scientist (DR1) at INRIA, a member of the Association for Computer Machinery (ACM), and a Senior Member of the IEEE. His main research areas are Visual Analytics, Information Visualization and Human Computer Interaction.
He received his PhD in Computer Science in 1996 from Université Paris-Sud. In 1997, he joined the Graphic Design group at the Ecole des Mines de Nantes, which he led from 2000 to 2001. In 2001, he was invited to join the Human-Computer Interaction Laboratory at the University of Maryland in the USA for one year. He was recruited by INRIA in 2002 as a confirmed researcher and became Senior Research Scientist in 2006. He is the Scientific Leader of the INRIA Project Team AVIZ that he founded in 2007.
He is the General Chair of the IEEE VIS Conference in 2014, an Associate Editor of the IEEE Transactions on Visualization and Computer Graphics (TVCG), and a member of the IEEE Information Visualization Conference Steering Committee and of the EG EuroVis Steering Committee. Until 2013, Jean-Daniel Fekete was the President of the French-Speaking HCI Association (AFIHM). He was Conference Chair of the IEEE InfoVis Conference in 2011 and Paper Co-Chair of the IEEE Pacific Visualization Conference in 2011.