Ninety Degree Edge Rotations in Graph Drawings

Abstract

We discuss a rotation-based variant of a geometric puzzle game presented in previous research. While the goal of the aforementioned puzzle game was to make a graph drawing planar by repeatedly swapping the endpoints of any selected edge with each other, the rotation variant presented here rotates an edge ninety degrees in either clockwise, or counter-clockwise direction. Fundamental properties are shown through proofs and a construction. Further analysis is done through random rotations on a large scale, as well as through a breadth-first approach. Unexpected behaviour, where certain patterns arise, was found by performing the operation sequentially in a non-random manner. Additionally, three other move variants are touched upon in less detail and used along with the rotation variant in a new geometric puzzle game. A user study was conducted to research preferred control schemes for two of the move variants.