Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13),\ldots, (1n)\}$. Then, will the graph be always planar?

The graph is easily seen to be bipartite with one part the set of odd permutations and the other part the set of even permutations. Upto the group $S_3$ it is trivial to see why $G$ is planar. The first nontrivial part is when the group is $S_4$. The degree is $3$ in this case, but I don't see the complete regular bipartite graph $K_{3,3}$ explicitly. But can $G$ have a $K_{3,3}$ minor? I don't think so. Also, what if I replace the set $S$ with the set of all transpositions? Any hints? thanks beforehand.