Transposition Cayley graphs are planar

You already have an answer regarding the first part of your question, but this uses the fact that with your given generating set, the Cayley graph is $(n-1)$-regular. What if we pick the generating set $\{ (12), (12\cdots n)\}$?

So: there is a full characterisation, due to Maschke (1896), of which finite groups admit planar Cayley graphs with respect to some generating set. Such groups are called planar.

The finite group $A$ is planar if and only if $A = B_1 \times B_2$ with $B_1 = 1$ or $\mathbb{Z}_2$, and $B_2 \in \{ \mathbb{Z}_n, D_n, S_4, A_4, A_5 \mid n \in \mathbb{N} \}$.

A proof can be found e.g. here, and the original article is the (aptly) named [Maschke, H. The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley's Color Diagrams. Amer. J. Math. 18 (1896), no. 2, 156–194.]. If you'd like to read it, a stable link is here.

In particular, $S_n$ for $n \geq 5$ admits no generating set such that its Cayley graph is planar, answering the second part of your question.


Your graph $G$ will not be planar for all $n \geq 5$. To see this, we use the well-known fact that every bipartite planar graph $H$ satisfies $|E(H)| \leq 2|V(H)|-4$, and hence has average degree less than $4$. Since your Cayley graph $G$ is $(n-1)$-regular and bipartite, it is not planar for all $n \geq 5$.