The 30th Annual Graph Drawing Contest shall be held in conjunction with the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023). The contest has two parts: the Creative Topic and the Live Challenge. They are briefly described below - details on both contests can be found on the contest webpage:

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

Creative Topic

The creative topic is provided a year in advance and focusses on free-form visualisation of a specific graph. Participants are invited to submit a creative drawing of this graph that evokes exploration and understanding the graph. The submissions will be judged by the contest committee. This year’s topic is Boardgame Recommendations.

Live Challenge

The live challenge will be held during the conference (exact date and time to be announced) in a format similar to a typical programming contest, where teams are presented with a collection of challenge graphs and have approximately one hour to submit their highest scoring drawings (either created manually, or automatically). This year the challenge will focus on minimizing crossings, when drawing a graph by assigning its vertices to a given set of locations.

Awards

Awards will be given to the top submissions in each of the contests.

Contest committee

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

We are happy to announce theFifth Computational Geometry Challenge, as part of CG Week in Dallas, TX, USA,  June 12-15, 2023.

As in previous years, the objective will be to compute good solutions to instances of a difficult geometric optimization problem. The specific problem chosen for the 2023 Challenge is 

        Minimum Coverage by Convex Polygons.

Description

Given a geometric region, P, in the plane, which may be a simple polygon or a polygon with holes. The task is to cover P with a collection,  C₁,…, C_k, of convex polygons, each contained within P.

Objective

Minimize k, the number of convex polygons in the cover. 

Motivation

Optimal coverage problems have an extensive history in Computational Geometry. In fact, the well-known SoCG logo shows that an optimal solution to the Minimum Cover by rectangles may include (rotated) rectangles whose vertices are not among those of the input polygon P, even in the case that P is an orthogonal simple polygon. It is also relevant in practical contexts, such as surveillance and robot navigation. The Minimum Cover by Convex Polygons problem is not only NP-hard, but was recently shown to be ∃R-complete, which most likely implies that it is not in the class NP.

Details of the competition (such as benchmark instances, data formats, and rules for submission and evaluation) will be announced in the coming weeks. Appropriate steps will be undertaken (e.g., by restricting the classes of feasible subsets) to ensure straightforward, automated verification of solutions.The contributors with the most outstanding solutions will be recognized at CG Week 2023 and invited to present their results, both at the event and in the proceedings.

We are looking forward to your contributions and welcome questions and comments! 

Instances

A large number and variety of input polygonal regions P will be provided for the competition. These will be released at a later time. (See below.)

Credit: This problem was suggested by Dan Halperin, Tel Aviv University.
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

Timeline

A first batch of test instances will be released in late September 2022; the actual benchmark instances for the Challenge will be released in October. The contest will close in early 2023.

• First test instances: September 30, 2022
• Contest instances:   October 28, 2022
• Contest Closes:        January 27, 2023

We are happy to announce the 4th Geometric Optimization Challenge, as part of CG Week in Berlin, Germany, June 7-10, 2022

As in the last year, the objective will be to compute good solutions to instances of a difficult geometric optimization problem.  The specific problem chosen for the 2022 Challenge is the following:

        Minimum Partition into Plane Subgraphs

Given a geometric graph G=(V,E), with vertices represented by points in the plane, and edges by straight-line connections between vertices. The task is to partition E into as few subsets E₁,…,E_k as possible, such that each subgraph G_i=(V,E_i) is plane: In the given geometric representation, line segments representing edges my touch at end points if and only if the corresponding edges are incident in G_i; no edges my cross, i.e., share points that are not segment end points.

The problem is related to a variety of classic problems, ranging from coloring and graph partitioning to extremal graph theory. For example, edge coloring in planar graphs H (for which it is a long-standing conjecture that it is NP-hard for graphs of maximum degree Δ=4 or 5  to decide whether they have an edge coloring with Δ colors) is a special case: From a straight-line drawing of H, slightly extend all line segments, so that they cross at the vertices of H, and nowhere else.

The related problem of partitioning a geometric graph into a minimum number of plane spanning trees has also received considerable attention.

Details of the competition (such as benchmark instances, data formats, and rules for submission and evaluation) will be announced in coming weeks; see the timeline below.

The contributors with the most outstanding solutions will be recognized at CG Week and invited to present their results, both at the event and in the proceedings.

We are looking forward to your contributions and welcome questions and comments!

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

Timeline:

• By August 19, 2020:    Release of first test instances
• September 19, 2021:  Contest instances, contest opens
• January 19, 2022:        Contest closes
• March 15, 2021:          Final versions of proceedings contributions due

Credit: This problem was suggested by Johannes Obenaus, FU Berlin.

The 29th International Symposium on Graph Drawing and Network Visualization will (hopefully!) take place in Tübingen, Germany, from September 14 to 17, 2021. As has been tradition since 1994, the symposium will be accompanied by a Graph Drawing Contest, allowing all community members to demonstrate their graph drawing skills in a fun competitive setting. The contest has two parts: the Creative Topics and the Live Challenge.

1. Live Challenge

Following popular tradition, a live challenge will be held during the symposium in a format similar to a typical programming contest. Teams are presented with a collection of challenge graphs and have approximately one hour to submit their highest scoring drawings. This year, the challenge focuses on

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

In the automatic category, teams use their own customized tools (or a lot of manual effort) to draw the graphs. Participation in this category can be.
In the manual category, teams solve (smaller) instances and submit their solutions via a dedicated tool, similar to the one used last year:

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

In case that the conference will be organized in an online or hybrid format, remote participation will also be possible in the manual category.
For more details, visit

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

2. Creative Topics

For your entertainment and inspiration, we have composed two nice graphs that you may draw with full artistic freedom.

1. Movie Remakes
   A movie remake is a production of a film that is based upon an earlier production. A remake tells the same story as the original but uses a different cast and may alter the theme or target audience. For this topic, you have the task to visualize a graph of movie remakes by different directors. The data contains a list of directors, and pairs of movies: the original and the remake (both with title, year, and directors). The data has been crawled from Wikipedia and consists of 91 directors and 102 pairs of movies. You are free to decide which parts of the data to visualize and how to visualize it.
2. Argumentation Network: The Great Devonian Controversy – A Logical Reconstruction
   The network shows a logical reconstruction of a scientific debate among 19th century geologists, namely the Great Devonian Controversy. The network contains 335 vertices which are of two types: statements and arguments. Each argument has one or more sentences as premises and one sentence as a conclusion. The network contains 1016 edges. The edges connect statements to statements and statements to arguments.

In both cases, you may visualize the graph in any way you like. Submissions will be judged on a list of criteria that includes, but is not limited to, readability, aesthetics, novelty, and design quality. The weighting of the criteria might be different for the two graphs. Submissions will be handled through EasyChair. For more details, visit

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

Submission deadline: September 08 2021 (23:59 PDT)

3. Awards

We are planning to award a monetary prize to up to three submissions in each of the four different categories.

We are looking forward to your submissions!

The Graph Drawing Contest Committee,
Philipp Kindermann (chair), Tamara Mchedlidze, and Wouter Meulemans