Is genus of this graph bigger than 2? Can you help me compute the genus of graph $G:$ $V(G)=\{u_1,\cdots,u_8,v_1,\cdots,v_5\}$ and $E(G)=\{u_1u_3,u_1u_4,$ $u_1u_5,u_1u_6,$ $u_1u_7,u_1u_8,$ $u_1v_2,u_1v_3, $ $u_2u_3,u_2u_4,u_2u_5,$ $u_2u_6,u_2u_7,$ $u_2u_8,u_2v_2,u_2v_3$ $,u_3u_5,u_3u_6,$ $u_3u_7,u_3u_8,u_3v_4,$ $u_3v_5,u_4u_5,u_4u_6,$ $u_4u_7,u_4u_8,u_4v_4,$ $u_4v_5,u_5v_1,$ $u_6v_1,u_7v_1,u_8v_1.\}$  Is  genus of this graph  bigger than 2 or eual to 2?
 A: On this site authors usually give an introduction to their problem, background information, what they have already tried and what sort of methods they are considering to enable the most appropriate answers to be given. Here's my approach which doesn't quite yet work...
If we start with this embedding of $K_{4,4}$ on the torus (from my answer to this question) you can see that we can fit $K_{4,5}$ on the double torus by adding a suitably placed handle on which we can place the 5th vertex and join it to 4 others. For instance, we could add vertex 9 joined to vertices 1, 2, 3 and 4 via a handle between faces 1-7-3-6 and 2-8-4-7.
In order to finish your graph we would then need to add edges/paths between 4 of the 5 green vertices and we can almost do that, apart from vertex 7 which is part of both faces which had the handle added to it and so it can only be joined to vertex 5. Thus vertex 7 must be your $v_1$. We can then add edges between vertices 5, 6 and 8 and vertex 9 (which is vertex 10 too, I didn't add its edges to the red vertices to simplify matters) can be joined to vertices 6 and 8 via the handle. 

However, it can't be joined to vertex 5, so my feeling is that this graph does not have genus 2. Algebraically we can prove that any embedding of $K_{5,4}$ must have all faces of size 4 except for either one of size 8 or two of size 6 and you will need to prove that any other type of embedding doesn't work similarly or cannot exist.
A similar case to your graph has the genus proved in this paper "The orientable genus of some joins of complete graphs with large edgeless graphs" (Ellingham and Stephens), maybe that will be useful for you in the future. Similarly, this paper might be relevant too.
A: An algorithm to compute the genus is implemented in Sage. The OP should type in his graph, and see what happens.
