Graph Drawing Live Challenge

Crossing minimization in book embeddings

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 reorder nodes and reassign edges to different pages. This category is for creating manual solutions without help of an automatic algorithm. Teams in this category will receive smaller challenge graphs. The tool has changed since last year's contest. Please download the new version.

The challenge focuses on minimizing the number of crossings in a book embedding with k pages. The input graphs are arbitrary undirected graphs and a maximum number of pages that may be used.

A book with k pages consists of k half-spaces, the pages, that share a single line, the spine of the book. A k-page book embedding of a graph is an embedding of a graph into a book with k pages such that all the vertices lie at distinct positions of the spine and every edge is drawn in one of the pages such that only its endpoints touch the spine.

Note that edges may only cross if they are assigned to the same page. We are looking for drawings that minimize the number of crossings. The results are judged solely with respect to the number of crossings; other aesthetic criteria are not taken into account. This allows an objective way to qualitatively evaluate a given drawing.

In this setting, a drawing can be specified by a) describing an ordering of the vertices along the spine and b) an assignment of the edges to the pages.

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.
• 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 five to ten graphs. The graphs will have up to a few thousand nodes.
• The graphs will have an initial k-page book embedding for the given value of k. For each graph, the team submitting the drawing with the smallest number of crossings 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.

File Format

For the GD2015 contest, an ASCII 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.

• The first number (N) indicates the number of nodes in the graph.
• The second number (K) is the maximum number of pages that may be used.
• The next N numbers describe a permutation of the node 0 to N-1 as they occur along the spine.
• The remainder of the file contains the edges. For each edge, the first value is the index of the source node, and the second value is the index of the target node. The third value is enclosed in rectangular brackets [ and ] and describes the page (in 0,…,K-1) to which that edge is assigned.
• The nodes are labeled from 0 to N-1 and the labels must be preserved for the output file as well.
• Comments are allowed as indicated below.
• The edge order is not important.
• The contest graphs will have a random start order and page assignment.
• All numbers are integers.

Sample File

Below is a simple example:

# Lines starting with # are comments and ignored
# First value is the number of nodes (N)
6
# Second value is the number of pages (K)
2
# Next N numbers describe a permutation of the nodes as they occur along the spine.
0
1
2
3
4
5
# Remaining lines are the edges.
# The first value is the source node.
# The second value is the target node.
# The third value is enclosed in rectangular brackets and describes the page to which that edge is assigned.
0 1 [1]                 # Edge between Node 0 and Node 1 on page 1
0 3 [0]                 # Edge between Node 0 and Node 3 on page 0
0 5 [0]                 # Edge between Node 0 and Node 5 on page 0
1 2 [1]                 # Edge between Node 1 and Node 2 on page 1
1 4 [0]                 # Edge between Node 1 and Node 4 on page 0
2 4 [1]                 # Edge between Node 2 and Node 4 on page 1
2 5 [0]                 # Edge between Node 2 and Node 5 on page 0
4 5 [1]                 # Edge between Node 4 and Node 5 on page 1
		

The left drawing below corresponds to this input file. This layout has 3 crossings and is not optimal. By moving node 5 between 2 and 3 and switching the edge (1,4) to the other page, the graph can be drawn without crossings; see the right drawing below. The edge (1,4) is drawn dashed simply for visualization improvement.

How to participate

The Live Challenge will be part of the 24th International Symposium on Graph Drawing and Network Visualization, and will take place in the evening of September 19, 2016 for one hour between 18:15 and 19:45 Eastern European Summer Time.

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 need to have java 8 installed on your laptop, and you can attempt to solve the problems using a supplied tool. You can already download the tool and familiarize yourself with its use here. <

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.

This year, the challenge will be run through an online submission system. This system is experimental, and we will still allow submission by usb (if you are attending the symposium) or by e-mail (if you are not attending the symposium - in this case the e-mail should arrive before the end of the contest). However, submission through the system is recommended. You can already visit the system and try out some test graphs here.