In mathematics, a rotation map is a function that represents an undirected edge-labeled graph, where each vertex enumerates its outgoing neighbors. Rotation maps were first introduced by Reingold, Vadhan and Wigderson (“Entropy waves, the zig-zag graph product, and new constant-degree expanders”, 2002) in order to conveniently define the zig-zag product and prove its properties. Given a vertex v and an edge label i , the rotation map returns the i 'th neighbor of v and the edge label that would lead back to v .
For a D-regular graph G, the rotation map R o t G : [ N ] × [ D ] → [ N ] × [ D ] is defined as follows: R o t G ( v , i ) = ( w , j ) if the ith edge leaving v leads to w, and the jth edge leaving w leads to v.
From the definition we see that R o t G is a permutation, and moreover R o t G ∘ R o t G is the identity map ( R o t G is an involution).
Special cases and properties
A rotation map is consistently labeled if all of the edges leaving each vertex are labeled in such a way that at each vertex, the labels of the incoming edges are all distinct. Every regular graph has some consistent labeling.A rotation map is π -consistent if ∀ v R o t G ( v , i ) = ( v [ i ] , π ( i ) ) . From the definition, a π -consistent rotation map is consistently labeled.