Der 30th Annual Graph Drawing Contest wird in Verbindung mit dem 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) stattfinden. Der Wettbewerb besteht aus zwei Teilen: dem Creative Topic und der Live Challenge. Beide werden unten kurz beschrieben - detaillierte Informationen zu beiden Wettbewerben finden Sie auf der Wettbewerbswebseite:

http://www.graphdrawing.org/gdcontest/2023/

Creative Topic

Das Creative Topic wird ein Jahr im Voraus bekannt gegeben und konzentriert sich auf die freie Visualisierung eines bestimmten Graphen. Die Teilnehmer sind aufgefordert, eine kreative Zeichnung dieses Graphen einzureichen, die die Erkundung und das Verständnis des Graphen fördert. Die Einreichungen werden vom Wettbewerbskomitee bewertet. Das Thema dieses Jahres lautet Boardgame Recommendations.

Live Challenge

Die Live Challenge findet während der Konferenz statt (genaues Datum und Uhrzeit werden noch bekannt gegeben) und folgt einem Format ähnlich einem typischen Programmierwettbewerb. Teams erhalten eine Sammlung von Herausforderungsgraphen und haben etwa eine Stunde Zeit, um ihre am höchsten bewerteten Zeichnungen einzureichen, die entweder manuell oder automatisch erstellt wurden. In diesem Jahr liegt der Fokus der Challenge auf der Minimierung von Kreuzungen beim Zeichnen eines Graphen durch Zuordnen seiner Knoten zu einem bestimmten Satz von Standorten.

Awards

Auszeichnungen werden für die besten Einreichungen in beiden Wettbewerben vergeben.

Contest committee

Philipp Kindermann, Fabian Klute, Tamara Mchedlidze, Wouter Meulemans (Vorsitzender) & Debajyoti Mondal

Wir freuen uns, die Fünfte Computational Geometry Challenge im Rahmen der CG Week in Dallas, TX, USA, am 12. - 15. Juni 2023, anzukündigen.

Wie in den vergangenen Jahren lautet das Ziel, gute Lösungen für Instanzen eines schwierigen geometrischen Optimierungsproblems zu berechnen. Das spezifische Problem für die Challenge 2023 lautet:

        Minimum Coverage by Convex Polygons.

Beschreibung

Gegeben sei eine geometrische Region P in der Ebene, die ein einfaches Polygon oder ein Polygon mit Löchern sein kann. Die Aufgabe besteht darin, P mit einer Sammlung von konvexen Polygonen C₁, ..., C_k zu bedecken, wobei jedes Polygon innerhalb von P enthalten ist.

Zielfunktion

Minimiere k, die Anzahl der konvexen Polygone in der Abdeckung.

Motivation

Optimale Abdeckungsprobleme haben eine umfangreiche Geschichte in der Computational Geometry. Tatsächlich zeigt das bekannte SoCG-Logo, dass eine optimale Lösung für die Minimum Cover by rectangles auch (gedrehte) Rechtecke einschließen kann, deren Eckpunkte nicht zu denen des Eingangspolygons P gehören, selbst wenn P ein orthogonales einfaches Polygon ist. Dies ist auch in praktischen Kontexten wie Überwachung und Roboternavigation relevant. Das Problem der Minimum Cover by Convex Polygons ist nicht nur NP-schwer, sondern wurde kürzlich als ∃R-vollständig gezeigt, was höchstwahrscheinlich bedeutet, dass es nicht in der Klasse NP liegt.

Details des Wettbewerbs (wie Benchmark-Instanzen, Datenformate und Regeln für Einreichung und Bewertung) werden in den kommenden Wochen bekannt gegeben. Geeignete Schritte werden unternommen (z. B. durch Beschränkung der Klassen zulässiger Teilmengen), um eine einfache, automatisierte Überprüfung von Lösungen sicherzustellen. Die Beitragenden mit den herausragendsten Lösungen werden auf der CG Week 2023 anerkannt und eingeladen, ihre Ergebnisse sowohl auf der Veranstaltung als auch in den Proceedings vorzustellen.

Wir freuen uns auf Ihre Beiträge und stehen für Fragen und Kommentare zur Verfügung!

Instanzen

Eine große Anzahl und Vielfalt von Eingangspolygonen P werden für den Wettbewerb bereitgestellt. Diese werden zu einem späteren Zeitpunkt veröffentlicht. (Siehe unten.)

Credit: Dieses Problem wurde von Dan Halperin, Tel Aviv University, vorgeschlagen.
Challenge Team: Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra
Advisory Board: Bill Cook, Andreas Fabri, Dan Halperin, Michael Kerber, Philipp Kindermann, Joe Mitchell, Kevin Verbeek

Zeitplan

Eine erste Gruppe von Testinstanzen wird Ende September 2022 veröffentlicht; die tatsächlichen Benchmark-Instanzen für die Challenge werden im Oktober veröffentlicht. Der Wettbewerb endet Anfang 2023.

• Erste Testinstanzen:        30. September 2022
• Wettbewerbsinstanzen:  28. Oktober 2022
• Wettbewerbsschluss:      27. Januar 2023

Wir freuen uns, die 4. Geometric Optimization Challenge als Teil der CG Week in Berlin, Deutschland, vom 7. bis 10. Juni 2022, anzukündigen.

Wie im letzten Jahr lautet das Ziel, gute Lösungen für Instanzen eines schwierigen geometrischen Optimierungsproblems zu berechnen. Das spezifische Problem für die Challenge 2022 ist wie folgt:

        Minimale Partition in ebenen Teilgraphen

Gegeben sei ein geometrischer Graph G=(V,E), wobei die Vertices durch Punkte in der Ebene und die Kanten durch Geradenverbindungen zwischen den Vertices repräsentiert werden. Die Aufgabe besteht darin, E in so wenige Teilmengen E₁,...,E_k wie möglich zu partitionieren, so dass jeder Teilgraph G_i=(V,E_i) eben ist: In der gegebenen geometrischen Darstellung dürfen sich die Liniensegmente, die Kanten repräsentieren, nur an den Endpunkten berühren, wenn die entsprechenden Kanten in G_i inzident sind; keine Kanten dürfen sich kreuzen, d.h., sie teilen keine Punkte, die nicht Endpunkte der Segmente sind.

Das Problem steht im Zusammenhang mit einer Vielzahl klassischer Probleme, von der Färbung und Graphpartitionierung bis zur extremalen Graphentheorie. Zum Beispiel ist die Kantenfärbung in planaren Graphen H (für die seit langem die Vermutung besteht, dass es NP-schwer ist, für Graphen mit maximalem Grad Δ=4 oder 5 zu entscheiden, ob sie eine Kantenfärbung mit Δ Farben haben) ein Spezialfall: Von einer geradlinigen Zeichnung von H aus dehnen Sie alle Liniensegmente leicht aus, sodass sie sich an den Vertices von H berühren, und sonst nirgendwo.

Das verwandte Problem, einen geometrischen Graphen in eine minimale Anzahl von ebenen Spannbäumen zu partitionieren, hat ebenfalls erhebliche Aufmerksamkeit erhalten.

Details des Wettbewerbs (wie Benchmark-Instanzen, Datenformate und Regeln für Einreichung und Bewertung) werden in den kommenden Wochen bekannt gegeben; siehe den Zeitplan unten.

Die Beitragenden mit den herausragendsten Lösungen werden auf der CG Week anerkannt und eingeladen, ihre Ergebnisse sowohl auf der Veranstaltung als auch in den Proceedings vorzustellen.

Wir freuen uns auf Ihre Beiträge und stehen für Fragen und Kommentare zur Verfügung!

Challenge Team: Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra
Advisory Board: Bill Cook, Andreas Fabri, Michael Kerber, Philipp Kindermann, Kevin Verbeek

Timeline:

• Bis August 19, 2020:    Veröffentlichung erster Testinstanzen
• September 19, 2021:  Wettbewerbsinstanzen, Wettbewerb beginnt
• Januar 19, 2022:          Wettbewerb endet
• March 15, 2021:          Endgültige Versionen der Beiträge für die Proceedings sind fällig

Credit: Dieses Problem wurde von Johannes Obenaus, FU Berlin, vorgeschlagen.

Das 29. Internationale Symposium über Graphzeichnen und Netzwerkvisualisierung wird vom 14. bis 17. September 2021 in Tübingen, Deutschland, stattfinden. Wie seit 1994 Tradition, wird das Symposium von einem Graphzeichnungswettbewerb begleitet, der allen Gemeindemitgliedern die Möglichkeit bietet, ihre Fähigkeiten im Graphzeichnen in einem unterhaltsamen, wettbewerbsorientierten Umfeld zu zeigen. Der Wettbewerb besteht aus zwei Teilen: den Creative Topics und der Live Challenge.

1. Live Challenge

In bewährter Tradition wird während des Symposiums eine Live Challenge in einem Format ähnlich einem typischen Programmierwettbewerb abgehalten. Teams erhalten eine Sammlung von Herausforderungsgraphen und haben etwa eine Stunde Zeit, ihre am besten bewerteten Zeichnungen einzureichen. In diesem Jahr liegt der Schwerpunkt der Herausforderung auf

        minimizing the planar polyline edge-length ratio on a fixed grid.

Im automatischen Bereich verwenden Teams ihre eigenen individuellen Tools (oder eine Menge manueller Arbeit), um die Graphen zu zeichnen. Die Teilnahme in dieser Kategorie kann remote erfolgen. Im manuellen Bereich lösen Teams kleinere Instanzen und reichen ihre Lösungen über ein dediziertes Tool ein, ähnlich dem im letzten Jahr verwendeten:

https://graphdrawingcontest.appspot.com/tool.jsp

Falls die Konferenz in einem Online- oder Hybridformat organisiert wird, wird auch in der manuellen Kategorie eine Remote-Teilnahme möglich sein. Für weitere Details besuchen Sie:

http://graphdrawing.org/gdcontest/contest2021/index.php?id=live-challenge

2. Creative Topics

Zur Unterhaltung und Inspiration haben wir zwei interessante Graphen zusammengestellt, die Sie mit voller künstlerischer Freiheit zeichnen können.

1. Film-Remakes
   Ein Film-Remake ist eine Produktion eines Films, die auf einer früheren Produktion basiert. Ein Remake erzählt die gleiche Geschichte wie das Original, verwendet jedoch eine andere Besetzung und kann das Thema oder die Zielgruppe ändern. Sie haben die Aufgabe, einen Graphen von Filmremakes verschiedener Regisseure zu visualisieren. Die Daten enthalten eine Liste von Regisseuren und Paare von Filmen: das Original und das Remake (beide mit Titel, Jahr und Regisseuren). Die Daten wurden von Wikipedia gecrawlt und umfassen 91 Regisseure und 102 Filmpaare. Sie können frei entscheiden, welche Teile der Daten Sie visualisieren möchten und wie Sie dies tun möchten.

2. Argumentationsnetzwerk: Die Große Devonische Kontroverse - Eine logische Rekonstruktion.
   Das Netzwerk zeigt eine logische Rekonstruktion einer wissenschaftlichen Debatte unter Geologen des 19. Jahrhunderts, nämlich der Großen Devonischen Kontroverse. Das Netzwerk enthält 335 Knoten, die zwei Typen haben: Aussagen und Argumente. Jedes Argument hat eine oder mehrere Sätze als Prämissen und einen Satz als Schlussfolgerung. Das Netzwerk enthält 1016 Kanten. Die Kanten verbinden Aussagen mit Aussagen und Aussagen mit Argumenten.

In beiden Fällen können Sie den Graphen beliebig visualisieren. Einreichungen werden nach einer Liste von Kriterien bewertet, zu denen Lesbarkeit, Ästhetik, Neuheit und Designqualität gehören, aber nicht darauf beschränkt sind. Die Gewichtung der Kriterien kann für die beiden Graphen unterschiedlich sein. Einreichungen werden über EasyChair abgewickelt. Für weitere Details besuchen Sie:

http://graphdrawing.org/gdcontest/contest2021/index.php?id=creative-topics

Einreichungsfrist: 8. September 2021 (23:59 PDT)

3. Auszeichnungen

Wir planen, einen Geldpreis für bis zu drei Einreichungen in jeder der vier verschiedenen Kategorien zu vergeben.

Wir freuen uns auf Ihre Einreichungen!

Das Graph Drawing Contest Committee,
Philipp Kindermann (Vorsitz), Tamara Mchedlidze, and Wouter Meulemans