Rotation map

In Mathematics, a rotation map is a function that represents a graph through a permutation on pairs of vertex name and edge label. Roughly speaking, given a vertex $v$ and an edge $i$, the rotation map that represents graph $G$ will return the vertex that is reached by traversing from $v$ through $i$ and the edge that would lead back to $v$, thus keeping track of the edges traversed during the walk on the graph.

Definition

For a $D$-regular graph $G$, the rotation map $Rot_{G}:[N]\times [D]\rightarrow [N]\times [D]$ is defined as follows: $Rot_{G}(v,i)=(w,j)$ if the $i$'th edge incident to $v$ leads to $w$, and this edge is the $j$'th edge incident to $w$.

See also

• Zig-zag product

References

• Reingold, O.; Vadhan, S.; Widgerson, A. (2000), "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors", 41st Annual Symposium on Foundations of Computer Science, doi:10.1109/SFCS.2000.892006

• Reingold, O (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291