Rotation map

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.

and an edge label

, the rotation map returns the

and the edge label that would lead back to

For a D-regular graph G, the rotation map

if the i th edge leaving v leads to w, and the j th edge leaving w leads to v. From the definition we see that

is the identity map (