Home Page
GD2008 CONTEST OVERVIEW MYSTERY GRAPH ELECTRICAL NETWORK SOCIAL NETWORK BIOLOGICAL NETWORK CHALLENGE

Graph Drawing Challenge (Upward Crossing Reduction)

Who has the best Sugiyama style layout?

As with last year's contest, 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 exist two categories in the challenge that are judged differently:

This year the challenge focuses on minimizing the number of crossings of upward grid drawings of graphs with edge bends. The challenge graphs will be directed, acyclic and non-planar. Multiple edges between the same pair of nodes may occur. In particular, all drawings must have the following properties:

The results are judged solely with respect to the number of edge crossings. Other aesthetic criteria such as symmetry of the placement or use of area are not taken into account. This allows an objective way to qualitatively evaluate a given drawing. With this challenge, we hope to attract (not exclusively) all teams that have developed an automatic Sugiyama-style layout or any alternative approach for directed acyclic graphs.

Here are some examples of allowed and forbidden situations. For the challenge, it does not matter whether the y-axis is oriented in mathematical convention with increasing coordinates towards the top, or in English reading direction with increasing coordinates towards the bottom, but in the drawings below, the origin (0,0) is near the bottom left corner, that is, the y-axis is drawn in mathematical convention.

Allowed:
2 crossings
Forbidden:
Node overlaps edge
Forbidden:
Edge segments overlap
Forbidden:
Edge bend on other segment
Forbidden:
Knockknee (bends on same location)

Here is an overview of the rules for the challenge:

Remote Participation

For those teams that cannot attend the conference but still wish to compete (in the automatic category), we allow remote participation. A few key points:

Graph Format

For the GD2008 contest, a modified 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.


Sample File

Below is a simple example:

# Lines starting with # are comments and ignored
# First value is NumNodes(N)
5
#
# Next N pairs are x and y coordinate values of each node
10 0 # Node 0
5 5  # Node 1
0 10 # Node 2
0 8  # Node 3
10 2 # Node 4
#
# Remaining lines are the edges.
# The first value is the source node.
# The second value is the target node.
# The values between [ ... ] are grouped in pairs as bend points (X,Y) 
0 2 [ 9 5 5 9 ] # Edge from Node 0 to Node 2 with bend points (9,5) and (5,9)
0 4 []          # Edge from Node 0 to Node 4 with no bend points
0 1 []          # Edge from Node 0 to Node 1 with no bend points
0 3 [ 0 1 ]     # Edge from Node 0 to Node 3 with bend point (0,1)
4 1 []          # Edge from Node 4 to Node 1 with no bend points
4 3 [ 5 4 ]     # Edge from Node 4 to Node 3 with bend point (5,4)
4 2 [ 10 9 ]    # Edge from Node 4 to Node 2 with bend point (10,9)
1 3 []          # Edge from Node 1 to Node 3 with no bend points
1 2 []          # Edge from Node 1 to Node 2 with no bend points
3 2 []          # Edge from Node 3 to Node 2 with no bend points

The diagram below corresponds to this input file. It displays the K5 in a legal upward layout, however the number of crossings in this layout is not optimal. In this picture, the origin (0, 0) is near the top left corner (English reading direction). If your software has the origin at the bottom left corner (mathematical convention), your image will be mirrored in y direction.


Legal notice