Information Technology Reference
In-Depth Information
We received two submissions in this category, both presenting the network in a very
nice way. Martin N ollenburg'ssubmission (see Fig. 1(a)) is a typical metro map draw-
ing with a very nice routing of lines, created using their ILP-based metro map layout
algorithm [1]. Fig. 1(b) shows Arturs Verza'ssubmission, which gives a clear picture of
the cluttered city center.
The winner in this category was Martin N ollenburg from the Karlsruhe Institute of
Technology, since we preferred the nicer global layoutofhissubmission, which allows
a user of the map to easily figure out possible connections.
3
Composers Graph
For this category, we used a data set that was already a contest graph in 2011. The
com-
posers graph
is a large directed graph, where its 3,405 nodes represent Wikipedia arti-
cles about composers, and its 13,382 edges represent links between these articles. This
graph has too many nodes and edges to be effectively presented in a straightforward
way. Therefore, this time the task was to select the about 150 most important nodes and
to create a drawing of a subgraph containing these nodes. Part of the task was to define
important
in a suitable way. The criterion should only depend on the given graph, not
on any other sources or knowledge. It was also allowed to filter outsomeedges between
important nodes using a reasonable criterion for filtering.
We received three submissions for this graph. Fig.2(a)showsthesubmission from
Remus Zelina et al.; they divided the composers into
influencers
and
influencees
(a
composer could appear twice) and then usedGirvanNewmanmodularization to obtain
asetofmodules. For selecting the most important composers, they used the corre-
sponding factor in the modularity formula as well as the pagerankalgorithm. They also
categorized the edges with respect to the module structure and selected only the most
important ones. The final layout was then obtained by applying a layered approach that
emphasized the module structure. The submission by Ulf Ruegg (see Fig. 2(b)) used
the notion of betweenness to select the most important nodes in the graph; the edges
were then selected as a maximum spanning tree, where the edges were weighed using
edge betweenness. The resulting tree was laid out with a stress minimization approach.
The third submission came again from Arturs Verza. He used centrality for selecting
the top 150 composers, removed transitive edges in the subgraph, and finally applied a
circular layoutalgorithm (due to lack of space we omit the drawing; it can be found on
the contest web page).
The winner in this category was the team Remus Zelina, Sebastian Bota, Siebren
Houtman, and Radu Balaban from Meurs, Romania, for their clear representation of
global as well as local structure.
4
Online Challenge
The online challenge, which took place during the conference, dealt with minimizing
theareainanorthogonal grid drawing. The challenge graphs were not necessarily pla-
nar and had at most fourincidentedges per node. Edge crossings were allowed and
their number did not affect the score of a layout. Since typical drawing systems first try
