Take an undirected graph $G$, where every vertex has at least two edges (we count self-loops as two edges). For each vertex $v$, we define a regular deg($v$)-gon. For each edge between $v_1$ and $v_2$, we glue one of the edges of their polygon together (arbitrarily). We never glue an edge to itself.

This will give us a surface (which will be compact if $G$ is finite). How many surfaces will there be, up to homeomorphism (or how do you calculate this number, or establish bounds on it)?

Note that different surfaces can pop up, depending on how you glue things together. For example, a vertex with two self-loops, it can be a torus or a Klein bottle or a projective plane or a sphere.

We have $\Pi_{v\in V(G)}2(\text{deg($v$)}-1)!$ as an upper bound (the factor $2$ is because of orientation).

9more comments