[Solved]: Calculating genus of graph

One way that always works and is relatively easy to turn into code is Edmond’s rotational embedding scheme. Let $G$ be a connected graph with vertices $V(G)={v_1, v_1, dotsc, v_p}$. For every vertex $vin V(G)$ choose a permutation $pi_v$ of the vertices adjacent to $v$. Then the collection of permutations $pi_{v_i}$ determine an embedding of $G$ in a orientable surface $S_n$ of genus $n$, and, conversely, every embedding of $G$ in $S_n$ is determined by some collection of permutations as described above. For example, consider $K_4$ with vertices labeled ${1, 2, 3, 4}$ and permutations $$begin{align} pi_1 &= (2 4 3) pi_2 &= (1 3 4) pi_3 &= (1 2 4) pi_4 &= (3 1 2) end{align}$$ The permutations will correspond to the counterclockwise order in which the adjacent vertices are encountered in the embedding (hence the term rotation). The permutations give rise to permutations, $pi$, of the directed edges, defined by $pi((v_i, v_j)) = (v_j, pi_j(v_i))$. In the example above, we’ll have $$begin{align} pi((2, 1))&=(1, pi_1(2)) = (1, 4) pi((1, 4))&=(4, pi_4(1)) = (4, 2) pi((4, 2))&=(2, pi_2(4)) = (2, 1) end{align}$$ and we’re back where we started, having generated a 2-cell $(2, 1, 4)$. Starting the process with the directed edge $(1, 2)$ gives rise to a 2-cell $(1,2,3,4,1,3,2,4,3)$ and we stop here, having used all 12 directed edges in $K_4$. We know that for an orientable 2-cell embedding in $S_n$ of a graph with $p$ vertices, $q$ edges, $r$ faces we’ll have $$ p-q+r=2-2n $$ in this case we have $p-q+r=4-6+2=0=2-2n$ so $n=1$, meaning that $K_4$ has genus no larger than 1. Of course, as presented this is a terribly inefficient algorithm, since there will be factorially many permutations for each vertex. There are some tweaks that will speed this up and there are some more modern approaches/modifications one could use (Edmond’s paper came out in 1960), but the upshot is still that there’s no efficient way to compute the genus of a graph.