  It can be shown that each permutation group $G \sqsubseteq S_n$ can be
embedded, in a well defined sense, in a connected graph with $O(n+|G|)$
vertices. Some groups, however, require much fewer vertices. For instance,
$S_n$ itself can be embedded in the $n$-clique $K_n$, a connected graph with n
vertices. In this work, we show that the minimum size of a context-free grammar
generating a finite permutation group $G \sqsubseteq S_n$ can be upper bounded
by three structural parameters of connected graphs embedding $G$: the number of
vertices, the treewidth, and the maximum degree. More precisely, we show that
any permutation group $G \sqsubseteq S_n$ that can be embedded into a connected
graph with $m$ vertices, treewidth k, and maximum degree $\Delta$, can also be
generated by a context-free grammar of size $2^{O(k\Delta\log\Delta)}\cdot
m^{O(k)}$. By combining our upper bound with a connection between the extension
complexity of a permutation group and the grammar complexity of a formal
language, we also get that these permutation groups can be represented by
polytopes of extension complexity $2^{O(k \Delta\log \Delta)}\cdot m^{O(k)}$.
The above upper bounds can be used to provide trade-offs between the index of
permutation groups, and the number of vertices, treewidth and maximum degree of
connected graphs embedding these groups. In particular, by combining our main
result with a celebrated $2^{\Omega(n)}$ lower bound on the grammar complexity
of the symmetric group $S_n$ we have that connected graphs of treewidth
$o(n/\log n)$ and maximum degree $o(n/\log n)$ embedding subgroups of $S_n$ of
index $2^{cn}$ for some small constant $c$ must have $n^{\omega(1)}$ vertices.
This lower bound can be improved to exponential on graphs of treewidth
$n^{\varepsilon}$ for $\varepsilon<1$ and maximum degree $o(n/\log n)$.
