In the chip-firing game, each vertex of a graph is assigned a number of chips. “Firing” a vertex corresponds to moving one chip from this vertex to each of its neighbors (or out-neighbors in the directed case). When a chip configuration can be reached from another one by a sequence of chip-firings, the two configurations are said to be equivalent.
The sandpile group of a graph or digraph is a group whose elements are configurations of chips on the vertices of the graph, quotiented by this equivalence relation. The number of elements of this group is equal to the number of spanning trees in the undirected case, and to the number of spanning in-arborescences rooted in a given vertex in the Eulerian directed case.
Rotor-routing is a way to describe a deterministic walk in a graph or digraph with a circular order on the neighbors of each vertex. Each vertex initially points to one of its neighbors, and when the walk arrives at some vertex \(v\) (pointing to some neighbor \(u\), say) the walk moves to the neighbor \(w\) of \(v\) succeeding \(u\) in the circular order around \(v\), and \(v\) is then updated to point to \(w\).
In addition to its interesting combinatorial properties, rotor-routing can be used to describe a simply transitive action of the sandpile group of a graph to its spanning trees. This action is defined with respect to a specific root vertex, and it can be proved that the action is “canonical” (that is, independent of the choice of the root vertex) precisely when the graph is planar and the circular order around each vertex corresponds to the order given by a planar embedding.
The main result of the paper is the description of a canonical simply transitive action of the sandpile group of any Eulerian digraph to the set of Eulerian tours with a natural compatbility condition with the circular ordering around each vertex, using a directed version of the rotor-routing action. Undirected graphs can be turned into Eulerian digraphs by replacing each edge by two arcs in both directions, and this canonical action thus generalizes existing results in the undirected case.