Minimizing the \(k\) in \(k\)-Plane Drawings

(This is a preliminary version of the 2025 challenge and rules, more details to follow soon.)

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:

  • Automatic: This category is for teams using their own tool. Since we assume that the tool contains special algorithms to solve the challenge automatically, these teams will receive larger challenge graphs. Manual fine-tuning is allowed.

  • Manual: This category is for teams using the provided graph editor. The graph editor does not contain any specific algorithm to solve the challenge. It allows only to change vertex locations. This category is for creating manual solutions without help of an automatic algorithm. Teams in this category will receive smaller challenge graphs. The tool is available in the submission system.

The challenge focuses of finding drawings of graphs that have as few crossings as possible per edge. In other words, the aim is to find a \(k\)-plane drawing of the graph with \(k\) being as low as possible, where a \(k\)-plane drawing is one where each edge has at most \(k\) crossings.

Here is an overview of the rules for the challenge:

  • The challenge will take place for one hour during the Graph Drawing Symposium.
  • Teams may consist of up to three participants each. Each team should bring their own computers and/or software tools to the challenge.
  • Each team is required to have a representative on sight during the challenge (Details on how this rule is going to be implemented will follow. It will be possible to name a representative in some shape or form who does not need to be a team member.)
  • Software tools for manually solving the challenge will be provided for each team with time available prior to the challenge to set-up and practice with the system.
  • At the start of the challenge, contestants will receive a collection of graphs in the format described below.
  • For each graph, the team submitting the \(k\)-plane drawing with the smallest \(k\) receives the highest score. Scores for other submissions of the same graph shall be weighed with respect to this value.
  • The team with the highest total score over all graphs wins.

\(k\)-Plane Drawings

We consider only straight-line \(k\)-plane drawings in this challenge. We require that no two vertices are placed on the same coordinate and that no vertex is contained in the interior of a segment forming an edge. A drawing is said to be \(k\)-plane if there are at most \(k\) crossings per edge. To count crossings we take the maximum number of crossings over all edges. Crossings will always be counted pairwise, i.e., if three edges or more cross in the same point each pair of edges is counted as one crossing.

All drawings have to use integer coordinates in the range \(0\) to a provided maximum value (see below for how this is specified). To avoid the grid-size being the limited factor we will always set the size of the grid to at least \(n^2\) where \(n\) is the number of vertices of the provided graph. Below two drawings of the same graph as examples. The graph is \(K_7\) minus one edge, we see that, unsurprisingly, a drawing with all vertices placed on the boundary of a disk is not always optimal.

Figure 1: A 4-plane drawing.
Figure 2: A 2-plane drawing of the same graph.

File Format

For the GD Contest 2023, 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:

  • nodes: An array with one element per node of the graph. Each element has the following entries:
    • id: The id of the node. Has to be an integer between 0 and #nodes-1.
    • x: The x-coordinate of the node. Has to be an integer between 0 and width.
    • y: The y-coordinate of the node. Has to be an integer between 0 and height.
  • edges: An array with one element per edge of the graph. Each element has the following entries:
    • source: The id of the source node.
    • target: The id of the target node.
  • width (optional): The maximum x-coordinate of the grid. Has to be a non-negative integer. If unspecified, the width is set to 1,000,000.
  • height (optional): The maximum y-coordinate of the grid. Has to be a non-negative integer. If unspecified, the height is set to 1,000,000.

Sample Instances

Below is a simple example of an input file:


{ "nodes": [
    { "id": 0, "x": 1, "y": 0 },
    { "id": 1, "x": 0, "y": 2 },
    { "id": 2, "x": 2, "y": 2 },
    { "id": 3, "x": 1, "y": 4 }],
  "edges": [
    { "source": 0, "target": 1 },
    { "source": 0, "target": 2 },
    { "source": 1, "target": 2 },
    { "source": 1, "target": 3 },
    { "source": 2, "target": 3 }],
  "width": 6,
  "height": 6
 }

Some more example instances and (non-optimal) solutions can be found here. The solution files are prepared in a way that they can be loaded into the submission tool of the 2024 contest, hence the addition of some underlying set of points to make this loading easily possible.

How to participate

The Live Challenge will be part of the 33rd International Symposium on Graph Drawing and Network Visualization, the precise date and location are going to be announced soon.

If you wish to participate in the manual category, you will attempt to solve the problems using the 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.

You may use at most one computer per team.

The challenge will be run through an online submission system. We are currently updating the system for the 2025 challenge, but you can play with the previous version for 2024 here. The problem currently loaded in the tool is unrelated to the one of 2025.