Drei Auszeichnungen für den Lehrstuhl I bei der GD 2024 in Wien

^{Fotos: Michael Kiran Huber}

Auf dem 32ten International Symposium on Graph Drawing and Network Visualization konnten sich im September in Wien gleich zwei Mitglieder unseres Lehrstuhls über Best Paper Awards freuen. Außerdem erreichte eines unserer Teams im Graph Drawing Contest den ersten Platz in der manuellen Kategorie der Live Challenge.

Best Paper Award, Track 1: Combinatorial and algorithmic aspects

In dem Artikel "The Density Formula: One Lemma to Bound Them All" stellt das Team bestehend aus Lehrstuhlmitglied Boris Klemz, sowie Michael Kaufmann (Uni Tübingen), Kristin Knorr (FU Berlin), Meghana M. Reddy (ETH Zürich), Felix Schröder (Charles University Prague) und Torsten Ueckerdt (KIT) die Density Formula vor - eine Gleichung, die, ähnlich der bekannten Eulerschen Polyederformel, eine Verbindung zwischen der Anzahl der Knoten, der Anzahl der Kanten und der Flächen einer Graphzeichnung beschreibt. Im Gegensatz zum klassischen Vorbild lässt sich die Density Formula allerdings auch auf Zeichnungen anwenden, die Kreuzungen enthalten und eignet sich dadurch zur Analyse der maximalen Kantenzahl sogenannter beyond-planar Graphklassen, bei deren Zeichnung kontrollierte Arten von Kreuzungen erlaubt sind. Dies wird von dem Team sowohl durch einheitliche und vereinfachte Beweise für bereits bekannte Ergebnisse, als auch durch völlig neue Resultate demonstriert, wofür sie mit dem Preis für das beste theoretisch orientierte Paper ausgezeichnet wurden.

Best Paper Award, Track 2: Experimental, applied, and network visualization aspects

Im Track der anwendungsorientierten Paper wurde »GraphTrials: Visual Proofs of Graph Properties« ausgezeichnet, an dem auch unser Kollege Felix Klesen als Teil eines elfköpfigen internationalen Teams beteiligt war. Das Paper beschäftigt sich mit Graphzeichnungen, die spezielle Eigenschaften (z.B. Zusammenhang oder Vollständigkeit) des gezeichneten Graphen hervorheben und den Betrachter dadurch überzeugen, dass der Graph diese Eigenschaften auch tatsächlich besitzt. In diesem Rahmen studieren und entwerfen Sie Richtlinien für Kriterien, die Zeichnungen erfüllen sollten, um als ein solcher »Beweis durch Zeichnung« überzeugen zu können.

Graph Drawing Contest: Live Challenge

Bei der Live Challenge des Graph Drawing Contest muss ein graphentheoretisches Problem für eine Menge gegebener Beispielgraphen innerhalb von einer Stunde gelöst werden. Dabei sind in der manuellen Kategorie keine Hilfsmittel erlaubt, in der automatischen Kategorie darf im Vorfeld vorbereitete Software eingesetzt werden. Die Aufgabe in diesem Jahr bestand darin, einen gegebenen Graphen so zu zeichnen, dass alle Knoten auf einer Auswahl vorgegebenen Punkte platziert werden und sich möglichst wenige Kanten kreuzen. Das Team bestehend aus Lehrstuhlmitgliedern Tim Hegemann und Johannes Zink konnte sich mit insgesamt 97 Kreuzungen den ersten Platz in der manuellen Kategorie erzeichnen.