CycleXings

A graph-drawing game by Andreas Bauer, Julian Vordermeier, Ignaz Rutter, and Michael Kaufmann

CycleXings is a two-player graph-drawing game, where players take turns at positioning the vertices of an n-vertex cycle to create a straight-line drawing of the cycle. The value n can be chosen arbitrarily, the default is n=10. Each vertex may be positioned exactly once, afterwards its position is fixed. Player 1, the maximize in the first round, seeks to maximize the number of crossings in the drawing. In contrast, Player 2 is the minimizer, who seeks to minimize the number of crossings. The first round ends when all vertices are positioned, i.e., after n moves. In the second round the roles are exchanged. The player creating more crossings when he is playing the maximizer wins the game.

The following pictures give an impression of the first round of a game. The first picture shows the game state after several moves. Green vertices have been placed by the maximizer, blue nodes by the minimizer. Black nodes have not yet been positioned. The red node is currently selected, it can either be moved and deselected to place it, or another node can be selected for movement. In the latter case the original position of the previously selected node is restored. In the second picture the selected node has been moved up and to the right, and it is now the minimizer's turn. The current number of crossings – 9 in this case – is displayed at the top. In the next picture the minimizer has moved the vertex at the top to the lower left, and has hence decreased the crossings to 3. Again, by moving one vertex to the very top, the maximizer increases to 11 crossings. In the final move of the round, the minimizer moves the last unpositioned node to the upper left, reaching a final crossing number of 4, which is acknowledged with a message box. Then the second round starts, where the second Player (blue) has to maximize the crossings.

Crossing minimization (in straight-line drawings) is certainly one of the most fundamental problems in graph drawing and has been shaping the research area of graph drawing over the past decades from the early NP-hardness proof due to Garey and Johnsone to a linear-time FPT algorithm and constant-factor approximations for bounded-degree graphs embeddable in a fixed orientable surface. See the recent survey that is to appear in the Graph Drawing Handbook for a complete treatment. The problem „dual“„ to crossing minimization, crossing maximization, is somehow a natural counterpart and has also been researched. The corresponding graph parameter is called the obfuscation complexity. Although, admittedly, crossing maximization lacks the strong practical motivation of its „primal“ counterpart crossing minimization. CycleXings combines these two problems into a single game, creating an additional twist by letting the players follow opposite optimization directions.

It seems an interesting problem to devise optimal strategies for the players, possibly also for more general graphs than n-vertex cycles.

See the documentation for some references.

CycleXings can be played on a regular PC running a recent version of Java. However, the better way to experience CycleXings is by using a tablet computer. In addition to the Java variant, we have an Android-based implementation, which can be played on smart phones and tablet computers that support the Android~4 OS.

For the java version, just download the file cyclexings.jar and run it with java -jar cyclexings.jar.

Java version for PC

The apk file can be installed on any Android device. It may be necessary to allow installation of third-party files in the settings.

APK file for tablet computer or smart phones running Android OS