Results of the 19th Graph Drawing Contest

This page reports on the results of the 19th Annual Graph Drawing Contest, held in conjunction with the 2012 Graph Drawing Symposium in Redmond, USA.

In contrast to previous editions, this year's Graph Drawing Contest was divided into an offline contest and a game contest. We introduced the game contest as a special event for celebrating Graph Drawing's 20th anniversary. The offline contest dealt with restricted area drawings and consisted of three categories. The data sets for the offline contest were published months in advance, and contestants could solve and submit their results before the conference started. The submitted drawings were evaluated according to aesthetic appearance and how well the area was used.

For the game contest, the task was to develop a computer game that is playable, relevant to graph drawing, and entertaining. Contestants had to bring their games to the conference and present them to conference attendees, who then scored the games.

Overall, we received 21 submissions: 14 submissions for the offline contest and 7 submissions for the game contest. The games were judged by 24 attendees.

Restricted Area

For the three categories in this topic, we asked for grid drawings but also restricted the allowed area of the drawings. Layouts exceeding this area were not permitted. Edges also had to be routed within the restricted area, but there were no restrictions concerning the shapes of edges. Though all contest graphs were planar, we allowed edge crossings.

Category A: Simple directed tree

The first data set for the restricted area topic was a simple directed tree with 371 nodes and an allowed area of 30×30 grid points. The area was chosen such that the tree could not be drawn with a usual tree drawing algorithm.

We received 6 submissions in this category, ranging from technically concise to artistically ambitious drawings. The submission by Remus Zelina et al. focuses on the long backbone of the tree which is visualized along the diagonal.

Submission by Remus Zelina et al. (click to enlarge)

On the other hand, the submission by Roman Prutkin visualizes the tree as a bee. Both drawings also visualize symmetries very nicely. The winner in this category was Roman Prutkin from Karlsruhe Institute of Technology, acknowledging the artistic value of his submission.

First Place: Roman Prutkin (click to enlarge)

Category B: Directed planar DAG

The second graph was a directed planar DAG, in fact a series-parallel digraph, with 172 nodes and 227 edges; the allowed area here was 22×30 grid points.

We received 4 submissions in this category, all visualizing the symmetric and series-parallel structure of the graph quite well. Only one of the submissions dared to draw the graph with crossings (just one crossing), but this clearly improved the display of the symmetric structures. We honored this courage by declaring Sergey Pupyrev from Ural Federal University as the winner in this category.

First Place: Sergey Pupyrev (click to enlarge)

Category C: Undirected and disconnected

The third graph was disconnected and consisted of five connected components. It contained 251 nodes and 266 edges, and the allowed area was 22×22 grid points.

In this category, we received 4 submissions as well. In some drawings, the connected components of the graph were drawn separately, in other drawings they were nested in order to save space and to improve the display of each component's overall structure. The submission by Joe Simons is an example of a more artistic drawing (showing the letters UCI), where components are separated.

Submission by Joe Simons (click to enlarge)

The drawing submitted by Remus Zelina et al. excellently displays the (symmetric and series-parallel) structure of the individual components. In this category, we preferred the best display of structure and declared the team of Remus Zelina, Sebastian Bota, Siebren Houtman, and Radu Balaban from Meurs, Romania, as the winner.

First Place: Remus Zelina et al. (click to enlarge)

Game Contest

For the game contest, the games had to be submitted before the conference and contestants could present their games to all Graph Drawing attendees during the conference. There were no further restrictions other than that the game should be related to graph drawing. We introduced the game contest as a special event for the 20th anniversary of the Graph Drawing conference, having already informally announced the contest in 2011 at the 19th Graph Drawing conference in Eindhoven.

Overall, 7 games were submitted, targeting quite varying platforms. These included Java-based games, games for touch-sensitive tablet computers (iPad, Android tablets), and even a conventional card game. Though not actually a computer game, the card game There is a graph... by Christopher Auer et al. was very popular, where players challenged each other to find graphs with certain properties. Attendees also heavily played the tablet games based on crossing minimization: CrossingX (by Tobias Brinkjost) and CycleXing (by Ignaz Rutter et al.). CrossingX challenges the player with the crossing minimization task in Sugiyama's algorithm, where the (layered) graph constantly moves from bottom to top while the player has to move the nodes on the layers to eliminate crossings. CycleXing is a two-player game, where one player has to increase the number of crossings in the drawing, while the other player tries to decrease them as much as possible. Yet another interesting game idea was based on visualizing planarity testing by switching trains (Derail by Christopher Auer et al.).

Joint First Places: CrossingX (left) and CycleXing (right) (click to enlarge)

For judging the games, we asked the Graph Drawing attendees to score the games, mainly on their fun factors, but also concerning their relevance to graph drawing. We provided scoring sheets, where attendees could give a score between 1 and 10 to each game; the higher the score the better the game. For getting a fair average score for each game, attendees should have played and scored all (or most) of the games. We calculated the average score for each game (where "no scores" did not count) and ranked the games accordingly.

In the final ranking two games were very close: CrossingX with a score of 8.5 and CycleXing scoring an 8.4; on the other hand CycleXing received more scores (24 compared to 18). Therefore, the judges decided to award two first prizes, also in appreciation of the effort for developing the games. Hence the winners in the game contest were Tobias Brinkjost (TU Dortmund) for CrossingX and the team of Andreas Bauer, Ignaz Rutter, Julian Vordermeier (all from Karlsruhe Institute of Technology), and Michael Kaufmann (University of Tübingen) for CycleXing.

The following table lists the submitted games and links to further information (if available).

Acknowledgments

The contest committee would like to thank the generous sponsors of the symposium and all the contestants for their participation.