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?

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.