Graph Drawing Contest - Graphs
Mystery Graph
The mystery graph has 71 nodes and 145 directed and labelled edges,
and represents a series of social or cultural events that got a fair
amount of news coverage this year.
As of now, parts of the data contained in the graph represent
planned events, that is, the data might be only partially up-to-date,
since some of the events are still ongoing (until August 8th).
We will not update the graph in the unlikely case that
the planned events change.
To solve this graph, two things are required:
-
To answer what events are represented by the graph.
-
To submit a drawing that displays the logical structure of the graph.
Graphs obtained by automatic layout are prefered, but manual fine
tuning is allowed.
Files
The mystery graph is available in two file formats.
Both files contain the same graph, that is, only one of both files is
needed.
The text file has a simple format:
-
First, it contains a list of all nodes.
A node is represented by a 3-letter symbol (e.g.,
XYZ
).
-
Then, it contains a list of all edges.
An edge is represented by an entry
ABC -> XYZ LLLLL
for a labeled edge from node ABC
to XYZ
.
The edge has the label LLLLL
.
Network from Electrical Engineering
This electrical network consists of 35 nodes and 48 edges.
The nodes are deeply nested.
It represents the architecture of a VLIW processor.
While the original network of the VLIW processor contained a mixture of
directed and undirected edges, we have simplified the network by using
only undirected edges.
This gives more freedom for laying out the graph.
The task is simply to produce the best possible automatic
drawing of the processor.
For this category, we ask for drawings created by a layout algorithm
without manual fine tuning.
Please indicate in your submission how
the drawing was obtained (software/algorithm etc.).
Files
The electrical network is available in two file formats.
Both files contain the same graph, that is, only one of both files is
needed.
The text file has a simple format:
-
First, it contains a list of all nodes.
A node is represented by a string (e.g.,
Pipline ctrl
).
-
Then, it contains the nesting/containment relationships of nodes.
An entry
A >> B
indicates that the node B
is contained in node A
.
-
Finally, it contains a list of all edges.
An edge is represented by an entry
A - B
for an undirected edge between node A
and node B
.
Network from Social Sciences
This graph represents the relationships between companies and
various persons in Germany.
It consists of 129 (or 130, see below) nodes and 271 edges.
The task is to produce the best visualization of this network while
including as much information as possible.
Static drawings, animations or entire tools to explore the graph are accepted
as submissions.
The graph is bipartite with two kinds of nodes:
-
Some nodes represent companies.
We included the top 25 publicly traded German companies (according to
Forbes 2007).
The companies are divided into business categories, allowing
a clustered or nested representation.
Additional data include revenue and market value in 2007.
-
Three nodes represent employee unions: ver.di, IG BCE and IG Metall.
-
The remaining nodes represent people, i.e., the top union officers and
the top managers in German business.
Union officers are employed by the corresponding union.
Top managers may be employed by companies and may serve in
supervisory boards of other companies.
For instance, since the company Porsche has a substantial ownership
share in the company VW, Porsche sends some managers to serve in the
supervisory board of VW.
There are 3 kinds of directed edges:
-
Edges from a person to a company: this person serves in the supervisory
board of the company.
-
Edges of class "A" from a company to a person: this person is employed
by that company. In this case, the person usually represents the
interests of its company in all its supervisory boards.
-
Edges of class "B" from a company to a person: this person was
recently employed by that company. In this case, it is disputable whether
the person acts on some company interests or on own private interests.
Very often, a former CEO moves into the supervisory board of the same
company simply to free the space for a new CEO, hence he/she still has
strong ties to that company even though he/she is no longer formally
employed by the company.
In other cases, a former CEO parted completely from a company (e.g.,
got fired) and now acts on own interests.
Information about the data
We thank Lothar Krempel for the idea of this graph.
The data was collected from Wikipedia and from various
business reports of the companies.
Some degree of data cleansing is already performed, but it is of course not
perfect.
Here are some additional notes:
-
The supervisory boards usually contain 10-25 people.
Not all of them are included in this graph.
We tried to include only those persons that connect different
companies.
-
The data provided in these graphs is mostly from 2007/early 2008.
Since the business topology is fast moving, some of the data
might already be out of date. The task is to visualize the
business situation of 2007/early 2008 in Germany.
-
The company names and manager names are given in simplified form
to reduce the size of labels in drawings.
We avoid German umlauts and reduce the names of people to
first name and family name, excluding any additional title
(Prof. Dr. Drs. h.c. mult. etc.).
-
Not all top managers are employed by the top 24 German companies.
For instance, Christian Streiff is a member of many German supervisory boards
but he is with Peugeot (a French car maker that does not occur in the
graph since it is not a German company).
-
In case the name of a company changed since a top manager left the
company, we use the new and current name of the company, not the old
name, to avoid that the same company is drawn by two different nodes.
-
Some big companies have multiple subsidiary companies with multiple
supervisory boards. Usually, we merged these boards into one data set,
with the exception of Dresdner Bank.
Dresdner Bank is a fully owned subsidiary of Allianz AG.
On the other hand, Dresdner Bank draws so many connections to other
businesses that it might be interesting to keep it separate.
We allow submissions that draw both as one node (Allianz/Dresdner Bank)
or as two nodes (Allianz node and Dresdner Bank node).
Both interpretations of the data are valid.
Files
The social science graph is available in a simple text format:
It has the following format:
-
First, it contains the companies and unions.
The format is:
string, integer, integer, integer, string
which is the company name, the revenue, the profit, the market value,
and the business category.
-
Then, it contains the names of the managers and union officers.
-
Then it contains the edges.
-
X -> Y
means that
person X serves in
the supervisory board of company Y.
-
X -a-> Y
means that company X
currently employs person Y (edge of class A).
-
X -b-> Y
means that company X
formerly employed person Y (edge of class B).
Biological Network
The biological network graph represents
the mTOR signalling pathway.
It contains 90 entities, 54 interactions and 85 inclusions.
The task is to produce the best drawing suitable for the biological domain.
For this category, we ask for drawings created by a layout algorithm
without manual fine tuning. Please indicate in your submission how the
drawing was obtained (software/algorithm etc.).
Files
The graph is available as a tab-delimited text format,
using a simplified
BioPAX (Biological Pathways Exchange)
representation:
It has the following format:
-
First, it contains the biological entities in the network.
The format is:
<entity ID> <type> <description>,
where <entity ID> is a unique identifying integer for the
biological entity,
<description> provides a short description of the entity, and
<type> can be one of many different kinds including protein,
small molecule, chemical reaction, and catalysis.
-
Then, it contains interactions in the network.
The format is:
<source entity ID> <target entity ID> <type>,
where interaction of the specified type goes from the source entity to
the target entity.
<type> can be:
- input: source of the interaction is input
to target of the interaction, which is a reaction,
- output: target of the interaction is an
output of the source of the interaction, which is a reaction,
- controller: source of the interaction is a
controller of the target of the interaction, which is a
catalysis for an interaction, or
- controlled: target of the interaction is a reaction,
controlled by a catalysis, which is the source of the
interaction.
-
The last part of the network contains inclusion relations.
The format is:
<owner entity ID> <child entity ID>,
where the child entity is part of the owner entity (e.g., a protein
that is part of a complex or a biochemical reaction that is part of a
pathway).
We thank Emek Demir of Memorial Sloan-Kettering Cancer Center, New York
for simplifying the format of the data.
Legal notice