Graph Drawing 2007
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.
As a continuation of last year,
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 the 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.
-
Software tools
will be provided for each team with time available prior to the
challenge to set-up and practice with the system.
Unfortunately, it appears that this year we will most likely not
be able to provide computers to each team as there does not appear to be
a lab available. However, we will make every effort to provide a few laptops
if possible.
-
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.
Please note that the graphs given will be planar but they may not be
3-connected, 2-connected, or even possibly connected graphs.
Consider embedding one small graph inside another graph!
-
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.
Remote Participation
For those teams that cannot attend the conference but still wishing to
compete, we are allowing remote participation.
A few key points:
- Participants should contact the committee prior to the contest, and
preferably as early as possible, to help determine the number
of remote teams and to coordinate the instructions.
- At the time of the challenge, remote teams will be able to access
an online location (website) to download the data sets and then
simply submit the results via email.
- Detailed submission instructions will be provided on this site
at a later time.
Graph Format
For the GD2006 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.
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)
Last Year's Sets
Below are the graphs from last year along with the best
submitted solution for each graph (from the contest itself).