We shall hold the Graph Drawing Challenge in a format similar to a typical programming contest. At the start of the challenge, teams of contestants will receive the collection of challenge graphs. After one hour, the teams will submit their final drawings and the team with the highest cumulative score wins.
Teams will be allowed to use any combination of software and human interaction systems to produce the best drawings. To accommodate both teams wishing to prepare for the challenge and teams wishing simply to participate, with no preparation, we will be providing, in advance, a small set of graph visualization tools. These tools are not necessarily meant to solve the problems at hand but are there to help the teams manually draw and manipulate the graphs. To further the development of new tools and to help promote tools already in existence, teams are also welcome and highly encouraged to create and bring their own software packages.
There will be two categories in the challenge that are judged independently:
The challenge focuses on minimizing the number of crossings in a straight-line upward drawing on a fixed grid. The input graphs are directed graphs without directed cycles.
A straight-line upward drawing is a drawing in which each directed edge is represented as a line segment such that the target vertex has a strictly higher y-coordinate than the source vertex. Two edges of an embedded graph are said to cross if they do not share an endpoint, but the interiors of their images intersect. The goal is to find a straight-line upward drawing which minimizes the number of crossings.
Here is an overview of the rules for the challenge:
For the GD2020 contest, a JSON format described below will be used. The contest graphs will be provided in this format and the final submissions should be prepared using the same format. A valid JSON file consists of the following entries:
Below is a simple example:
{ "nodes": [ { "id": 0, "x": 1, "y": 0 }, { "id": 1, "x": 1, "y": 1 }, { "id": 2, "x": 2, "y": 1 }, { "id": 3, "x": 0, "y": 2 }, { "id": 4, "x": 2, "y": 2 }], "edges": [ { "source": 0, "target": 1 }, { "source": 0, "target": 2 }, { "source": 0, "target": 3 }, { "source": 1, "target": 4 }, { "source": 2, "target": 3 }], "width": 2, "height": 2 }
The left drawing below corresponds to this input file. This layout has on crossing and is not optimal. By moving the nodes 1 and 4 to the left and the node 3 to the right, the graph can be drawn crossing-free; see the middle drawing below. The right drawing is also crossing-free, but it is invalid as the edge between nodes 0 and 3 as well as the edge between nodes 2 and 3 are not upward.
The Live Challenge will be part of the 28th International Symposium on Graph Drawing and Network Visualization, and will take place on TBA (September 2020).
If you are attending the Graph Drawing Symposium, you can choose to participate in either the manual or automatic category. In either case, you will need to bring an internet-enabled laptop or other device to the conference. If you wish to participate in the manual category, you will attempt to solve the problems using a supplied tool.
If you wish to participate in the automatic category, you can use any software you wish to solve the problems, including the supplied tool (however, problems instances will be much larger than in the manual category).
If you are not attending the symposium, you can still participate remotely in the automatic category. In either case, you may use at most one computer per team.
The challenge will be run through an online submission system. You can already visit the system and try out some test graphs.