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, two members of our chair were delighted to receive Best Paper Awards in September in Vienna. Additionally, one of our teams won first place in the manual category of the Live Challenge in the Graph Drawing Contest.

Best Paper Track 1: Combinatorial and Algorithmic Aspects

In the paper "The Density Formula: One Lemma to Bound Them All," the team consisting of chair member Boris Klemz, along with 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), presents the Density Formula—a formula similar to the well-known Euler's Polyhedron Formula that describes a relationship between the number of vertices, edges, and faces in a graph drawing. Unlike the classical counterpart, the Density Formula can be applied to drawings that include crossings and is thus suitable for analyzing the maximum number of edges in so-called beyond-planar graph classes, where drawings allow controlled types of crossings. The team demonstrated this through uniform and simplified proofs for already known results and completely new findings, earning them the award for the best theoretically oriented paper.

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

In the track for application-oriented papers, "GraphTrials: Visual Proofs of Graph Properties" was awarded, a paper involving our colleague Felix Klesen as part of an eleven-member international team. The paper deals with graph drawings that highlight special properties (e.g., connectivity or completeness) of the drawn graph and thus convince the viewer that the graph indeed possesses these properties. In this context, they study and design guidelines for criteria that drawings should meet to serve as a "proof by drawing."

Graph Drawing Contest: Live Challenge

In the Live Challenge of the Graph Drawing Contest, a graph-theoretical problem for a set of given example graphs must be solved within one hour. No aids are allowed in the manual category, while pre-prepared software may be used in the automatic category. The task this year 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. The team comprising chair members Tim Hegemann and Johannes Zink managed to achieve first place in the manual category with a total of 97 crossings.