We know that planar graphs have $O(1)$ degree.


We know balanced (each color has same number of vertices) complete bipartite graphs have genus $O(n^2)$.



> 
> 1. If maximum and average degree are $O(n^\alpha)$ where $\alpha\in[0,1]$ then is genus also $O(n^\alpha)$?
> 2. If maximum degree is $O(n^\alpha)$ where $\alpha\in[0,1]$ then is genus also $O(n^\alpha)$? (this is weaker than $1.$)
> 
> 
> 



Is bipartite graph genus bound by $O(\mbox{max deg})$?
The answer is no. [Hossein Namazi, Pekka Pankka, Juan Souto](https://arxiv.org/abs/1208.2130) showed that [expander graphs](https://en.wikipedia.org/wiki/Expander_graph) have genus that is linear in the number of vertices. You can construct bipartite, bounded degree expanders.


