Graph Drawing Challenge (Area Minimization)

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.

The challenge this year shall focus on area minimization of straight line planar grid drawings. In particular, all drawings must

  • use straight lines,
  • be planar,
  • have all vertices on integer grid locations, and
  • use smallest area possible.

While such drawings are not necessarily the best, area minimization is an important aesthetic criterion, which is well-known and difficult to compute. Moreover, this particular challenge offers an objective way to qualitatively evaluate a given drawing. 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 one to three participants each. Each team may bring their own computers and/or software tools to the challenge.
  • Computers and software tools 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 be undirected simple planar graphs with twenty to two hundred vertices.
  • For each graph, the team submitting the drawing with the smallest area shall receive 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.

Graph Format

For the GD 2006 contest, we will use a modified ASCII format described below. The contest graphs will be provided in this format and the final submissions should be prepared using the same format.

  • The first number indicates the number of nodes in the graph.
  • The next 2N double (actually, integers in our case) values are X Y pairs for each node, indicating its position, which initially are random values.
  • The remaining values are integer pairs <a b> indicating an edge exists between nodes A and B.
  • The nodes are labeled from 0 to N-1 and the order from the input file must be used in the output file as well.
  • The contest graphs will not contain comments though they are allowed.
  • Edge order is not important.
  • The contest graphs will have random start locations for the nodes.

Sample File

Below is a simple example.

# Lines starting with # are comments and ignored
# First value is NumNodes(N)
4
# Next N pairs are X,Y (double/integer) coordinate values of each node 0,1, N-1
0 0  # Node 0
0 5  # Node 1
5 5  # Node 2
5 0  # Node 4

# Remaining pairs of INTEGER values are undirected edges Ns, Ne
0 1      # Edge from Node 0 to Node 1
0 2
0 3
1 2
1 3
2 3

# Here we defined a 4-clique (with 1 crossing)