Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with $n$ vertices of color $1$ and with $n$ vertices of color $2$.
What is the maximum number of edges that a genus $g$ graph $B_{n,n}$ can have? Are there any good references for this topic?
Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with $n$ vertices of color $1$ and with $n$ vertices of color $2$.
What is the maximum number of edges that a genus $g$ graph $B_{n,n}$ can have? Are there any good references for this topic?
Let's flesh out Chris Godsil's answer after the recent bump.
Euler's formula tells us that $V-E+F=2-2g$, where $V$, $E$ and $F$ are the number of vertices, edges and faces respectively in an embedding of $G$. The smallest possible faces in an embedding of a bipartite graph are 4-cycles, so, by counting the edges round each face, $E \geq 4F/2$, i.e. $F \leq E/2$, with equality if and only if all faces are 4-cycles. Rearranging gives $E \leq 2V -4 + 4g$.