[Solved]: Calculating genus of graph

Problem Detail: 

How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search.

Asked By : Interloper

Answered By : Rick Decker

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 $v\in 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33219