Information Technology Reference
In-Depth Information
(a) initial
(b) best automatic
Fig. 3.
Challenge graph with 64 nodes and 124 edges: (a) initial layoutand(b)bestautomatic
result by the team of Mchedlidze et al
to minimize the number of crossings, which might result in long edges increasing the
required area, we were in particular interested in the effect of allowing crossingsonthe
quality of layouts when trying to reduce the area.
The task was to place nodes, edge bends, and crossingsoninteger coordinates so
that the edgerouting is orthogonal and the layout contains no overlaps. At the start of
the one-hour on-site competition, the contestants were given five graphs with an initial
legal layout with a large area. The goal was to rearrange the layouttoreduce the area,
defined as the number of grid points in the smallest rectangle enclosing the layout. Only
the area was judged; other aesthetic criteria, such as the number of crossingsoredge
bends, were ignored.
The contestants could choose to participate in one of two categories:
automatic
and
manual
. To determine the winner in each category, the scores of each graph, determined
by dividing theareaofthebestsubmission in this category by the area of the current
submission, were summed up. If no legal drawing of a graph was submitted (or a draw-
ing worse than the initial solution), the score of the initial solution was used.
In the automatic category, contestants received six graphs ranging in size from 20
nodes / 29 edges to 100 nodes / 182 edges and were allowed to use their own sophis-
ticated software tools with specialized algorithms. Manually fine-tuning the automati-
cally obtained solutions was allowed. Fig. 3 shows a challenge graph from the automatic
category with 64 nodes, 124 edges, and a very bad initial layout. The best obtained re-
sult improved the area from 1089 to 192. With a score of 4.964, the winner in the
automatic category was the team of Tamara Mchedlidze, Martin Nollenburg and their
