On learning of the lattice structure of the system of rooted spanning trees of a plane graph, I was hopeful that the theory would extend in a nice way to unrooted trees. For each choice of root and outer face, we have a distributed lattice, and the set of state transition systems formed in this way for different roots in a fixed graph share the same set of vertices and many of their edges. Different choices of root and outer face lead to different orientations on the edges, but we already know of an unoriented structure that generalizes distributed lattices, namely media. If we form a state transition system in which the states are the spanning trees of a plane graph, and the transitions are formed by replacing one of the edges at any vertex by a cyclically adjacent edge at the same vertex, is the result a medium?

The short answer: no, not generally. The longer answer:

To begin with, we might as well assume that the graph \(G\) is biconnected, because the spanning trees on either side of any articulation point behave independently. If \(G\) contains an odd face, one can find a system of spanning trees containing all but one edge of that face, the transitions among which form an odd cycle in the rotation graph. And if \(G\) contains a vertex of odd degree (in a biconnected graph), one can find a system of spanning trees containing only one edge at that vertex, the transitions among which form an odd cycle in the rotation graph. So, if the rotation graph is to be a medium, \(G\) must be bipartite and Eulerian.

I was hopeful that, analogously to my results on flip graphs, the obvious necessary conditions would also be sufficient, but it was not to be. The simplest examples of bipartite Eulerian graphs are even cycles, which give rise to even cycle rotation graphs, so far so good. The next graph I tried was a 4-cycle with doubled edges:

4-cycle with doubled edges

Its spanning trees consist of any capitalization of three of the four letters. There are 32 spanning trees: four choices of three letters, times eight capitalizations. A rotation either changes the capitalization of a letter, or replaces a letter with the adjacent missing letter with the same capitalization. The states involving a single choice of three letters form a cube, and the states involving any two adjacent choices of three letters form a 4-dimensional hypercube. However, it does not link up to form a 5-cube: if you start at any state, and repeatedly rotate in such a way that each rotation changes which three of the four letters are included, then after four rotations you will return to the same cube but with the capitalizations cyclically shifted by one position, while in a 5-cube this sequence of four transitions should return you to your starting point. In fact, the rotation graph of the doubled 4-cycle is not even a partial cube.

twisted 5-cube

So, if it is possible or useful to characterize the plane graphs that form partial-cube rotation graphs, the characterization is more complicated than simply avoiding odd cycles and odd vertices. Alternatively, perhaps the twisted 5-cube, and rotation graphs more generally, have some useful structure other than as a partial cube...