Three Awards for Chair I at GD 2024 in Vienna

^{Fotos: Michael Kiran Huber}

At the 32nd International Symposium on Graph Drawing and Network Visualization in Vienna, two members of our chair received Best Paper Awards. Additionally, one of our teams achieved first place in the manual category of the Live Challenge in the Graph Drawing Contest.

Best Paper Award, Track 1: Combinatorial and Algorithmic Aspects

In the paper "The Density Formula: One Lemma to Bound Them All," Boris Klemz and his coauthors Michael Kaufmann (University of Tübingen), Kristin Knorr (FU Berlin), Meghana M. Reddy (ETH Zurich), Felix Schröder (Charles University Prague), and Torsten Ueckerdt (KIT) present the Density Formula — a formula that, similar to Euler's well-known Polyhedron Formula, describes a relationship between the number of vertices, edges, and regions in a graph drawing. Unlike its classical counterpart, the Density Formula can be applied to drawings that contain crossings and is thus suitable for analyzing the maximum number of edges in so-called beyond-planar graph classes, whose drawings allow controlled types of crossings. The team demonstrated this by means of uniform and simplified proofs of established results, as well as completely new findings, earning them the award for the best theory focused paper.

Best Paper Award, Track 2: Experimental, Applied, and Network Visualization Aspects

In the application focused track, "GraphTrials: Visual Proofs of Graph Properties" was awarded, a paper involving our colleague Felix Klesen as part of a team of eleven internal researchers. The paper deals with graph drawings that highlight special properties (e.g., connectivity or completeness) of the drawn graph, thereby convincing the viewer that the graph indeed possesses these properties. In this context, they study and design guidelines for criteria that drawings should satisfy to serve as such a "proof by drawing".

Graph Drawing Contest: Live Challenge

In the Live Challenge of the Graph Drawing Contest, a specific graph-theoretical problem has to be solved for a given set of graphs within a time frame of one hour. While participants in the automatic category are allowed to utilize pre-designed software to achieve this goal, the manual category prohibits any sort of tool-assistance. This year's challenge was to draw a given graph so that all vertices are placed on a selection of given points with as few edge crossings as possible. Our team comprising Tim Hegemann and Johannes Zink managed to achieve first place in the manual category with a total of 97 crossings.