23rd International Symposium on
Graph Drawing & Network Visualization
September 24-26, 2015, Los Angeles, CA, USA
Home   •   23rd International Symposium on Graph Drawing and network Visualization

Graph Drawing Creative Topics

Topics

We have two creative topics, that are judged independently:

  • Graph classes: This graph models a set of well-known subclasses of planar graphs and their relations.
  • Tic Tac Toe: This graph contains all possible board positions and moves in the game of Tic Tac Toe.

Participants may submit drawings of both graphs (or only one graph).

Graph Classes

The Information System on Graph Classes and their Inclusions (ISGCI) is an initiative to provide a large database of graph classes and their relations, as well as the complexity of several problems that are hard on general graphs. So far, data of 1,511 graph classes and 179,111 inclusions has been collected.

For the first creative topic, you need to draw the graph of the graph classes provided by the ISGCI database that are planar. Each node represents a graph class, and each (directed) edge represents an inclusion. For example, the edge from "outerplanar" to "cactus" says that every cactus is outerplanar.

The graph has 65 vertices and 101 edges. The graph is presented in the GraphML File Format.

The resulting layout of the graph should contain the label of the vertices, provided as the description of the nodes, and should give a good overview on the hierarchy of the graph classes.

The graph is available here.

Tic Tac Toe

Tic Tac Toe is a tactical two-player game in which two players take turns entering symbols ('X' or 'O') into cells of a three by three grid, with the objective of creating a row, column, or diagonal of equal symbols. The game is famous for its relative simplicity.

For the second creative topic, you are asked to draw the graph of all possible Tic Tac Toe game states, in a way that shows as much of the structure and hidden information in the graph as possible.

Each node represents a class of symmetric board positions, and there is an edge between two nodes u and v if a board position from v can be reached from a board position from u.

The graph has 765 vertices and 2096 edges. The graph is presented in an ASCII text file, with the following structure:

  • The first 765 lines of the file each contain a string of 9 characters, describing a board position. The string encodes the state of each cell in lexicographic order. Each characters can be an 'X', an 'O', or a '-', indicating an empty cell. Recall that each vertex of the graph represents a class of symmetric board positions; an arbitrary element from the class has been chosen to describe it.
  • The next 2096 lines of the file each contain a tuple of numbers, in the form "(a,b)", where a and b are integer indices to the list of vertices (starting from 1).

The graph is available here.

Evaluation

For the creative topics, you are completely free to use any drawing style you wish. Your submissions will be judged both on aesthetic value and on the clarity of information displayed.

Submission

Electronic submissions (by email) must be received by September 21 (23:59 CEST) and should include the following information:

  • Names and email addresses of the contributors.
  • A picture (or other kind of visualization) illustrating the graph. PDFs are preferred.
  • A brief description on how the graph and layout were produced.

If your drawing requires special printing because of size, resolution, or color constraints, you are encouraged to submit via hard-copy. In this case, please contact us in advance and make sure that your submission is received no later than September 18.

Please send your contest submissions to:

Maarten Löffler
PO Box 80.089
3508 TB Utrecht
The Netherlands