What is the minimum number of vertices needed to represent a solid of genus $n$ in $\Bbb R^3$? The image below shows a $9$-vertex polyhedron that is topologically equivalent to a torus, and hence has genus $1$.
                           
The question is: what is the smallest number of vertices needed to represent a surface of genus $n$ in $\Bbb R^3$? Self-intersections are allowed, although I doubt they are necessary in any minimal examples. Labelling this as $f(n)$, this example shows that $f(1)\le9$ and obviously $f(0)=4$ (a tetrahedron is topologically equivalent to a sphere, and nothing smaller is non-planar. I claim that $f(1)=9$, i.e. there are no smaller 
polygons than the one above that maintain homeomorphism to a torus, although I don't see how to prove it. Can you generalize these two examples to an $n$-genus solid and get a bound on $f(n)$? Lower bounds seem quite hard to prove, though.
Edit in response to some of the comments: I believe that this problem can be tackled purely combinatorially, as my answer below hints at. The question boils down to this: Given a set $F$ of "oriented" three-element sets (i.e. ordered only up to cyclic permutation), define $V=\bigcup F$ and $E$ as the set of two-element subsets of some $f\in F$. This defines the set of vertices, edges, and faces. That this constitutes a polygon is the demand that every $\{e_1,e_2\}\in E$ is a subset of exactly two elements of $F$, once in the same direction as the cycle and once in the opposite direction, and the genus of the resulting surface can be calculated from $|V|-|E|+|F|=2-2g$. The orientation of elements of $F$ ensures that the resulting polygon is orientable, and then we can simply ask what is the smallest $k$ such that there exists such an arrangement with $|V|=k$ and $g=n$.
This mapping is justified by the classification theorem for closed surfaces, which says that the above conditions imply that the polyhedron is homeomorphic to a set of disconnected multiple tori of various genuses. And noting that one can connect the pieces by replacing two triangles on each surface with a triangular prism (which lowers the overall Euler characteristic by $2$), we see that under the reasonable assumption that $f(n)$ is non-decreasing, it follows that any minimal $k$ satisfying the combinatorial assumptions must describe a connected $n$-torus, which was our original goal.
 A: A general solution is still unknown, but I have a counterexample to the claim $f(1)=9$, in the form of a polyhedron with $7$ vertices and still equivalent to a torus. If the vertices are $v_1,\dots,v_7$, then the face assignment is $(v_1,v_2,v_4),(v_4,v_3,v_1)$ and cyclic rotations of this adding $n=0,\dots,6$ to each index in the set, for a total of $14$ faces. (Note that as in the OP these faces are "oriented sets" determined up to cyclic permutation of the three vertices.) The edges form a complete graph $K_7$, for a total of $21$ edges, and it is easily verified that each edge touches two faces, once in each direction, so it is locally homeomorphic to $\Bbb R^2$ and orientable. Then since $V-E+F=7-21+14=0=2-2g$, we get $g=1$, so it is also toroidal. Thus $f(1)\le 7$. Pictures are a little harder to make, since it seems to be self-intersecting under most attempts at vertex arrangement, but below is a topologically equivalent mapping onto an actual torus.
                                                

Edit: An exhaustive computer search has shown that the stated conditions are impossible to satisfy for $|V|<7$ (although there is one polyhedron on $6$ vertices with $\chi=1$), so $f(1)=7$.

By taking connected sums, we can easily iterate this construction to get an upper bound on $f(n)$. Given a $k$-vertex representation of a genus $n$ surface, remove one face from the surface and one face from the above $7$-vertex torus, then glue the holes together. The resulting surface has genus $n+1$ and $k+4$ vertices (because three vertices are overlapped with existing vertices), so we get the bound $f(n+1)\le f(n)+4$ and in particular $f(n)\le3+4n$. One remark: the case $f(0)=3$ corresponds to a triangle with two faces, one oriented up and the other down; this is not excluded as a valid surface of genus $0$ by the combinatorial interpretation, and I leave it to the reader to decide if this is a valid solution to the original question.

But we're not done yet - there's one more optimization we can do. Assuming we are just cobbling tori of this form together, the process above will construct a long line of tori. But we can fold the object onto itself, say by taking one end and gluing it to the other end, which eliminates three vertices and raises the genus by one as well. The prerequisite for not unduly affecting the $V-E+F$ equation is that the two targeted faces must not share a vertex, and indeed must be separated by at least two vertices (i.e. any path from a vertex of one face to a vertex of the other face "the long way round" must contain at least four vertices) so that no edges get folded on top of each other.
The simplest case of this is to fold the two ends together to make a ring of tori instead of a line - this is first possible for the three hole torus construction. At this point we have a ring of $n\ge3$ tori forming a genus $n+1$ surface and using $4n$ vertices (which proves $f(n)\le4n-3$ when $n\ge4$). But it gets better. Suppose that $v_{1,2,4}$ of torus $t_n$ is connected to $v_{6,3,5}$ of each $t_{n+1}$ in the ring, so that $v_7$ is unique to each torus and $v_{1,2,4}$ are shared between two tori. We will use the face $v_{4,6,7}$ of each torus as a connection point - note that this face is one edge away from the equivalent face on the next torus.
So now consider $n$ rings of $n-1$ tori each, and connect every ring to every other ring in a giant $K_n$ mimic. The rings act as big vertices, with $n-1$ connection points to the other vertices. Note that in the worst case we have three adjacent connection points in a triangle, which since the connection points are separated by one edge the triangle cycle separates the connection point from itself around the cycle by three edges, which as mentioned above is sufficient to maintain all edges so that the genus is not affected any more than it should be. Now for the accounting: each ring is $4(n-1)$ vertices, for a total of $4n(n-1)$, and there are $n(n-1)/2$ connections, each saving $3$ vertices each, so we count $5/2n(n-1)$ total vertices. For the genus, since $g-1=-\chi/2$ is additive over disconnected pieces, the genus of the rings is $n(n-1)+1$, and each connection raises the genus by $1$, so the full structure has genus $3/2\,n(n-1)+1$. Thus $f(3/2\,n(n-1)+1)\le5/2\,n(n-1)$, or $$f(n)\le\frac53n\quad\mbox{for infinitely many }n;\qquad f(n)\le\left(\frac53+\epsilon\right)n\quad\mbox{for sufficiently large }n.$$

I highly suspect that $f(n)\ge n$ or at least $f(n)=\Theta(n)$, but a proof is of course not forthcoming. One thing that can be done in the way of lower bounds comes from the observation that since each edge touches two faces and each face touches three edges, $3F=2E$, so $2-2g=V-E/3$, and if $|V|=f(n)$, then since $E\le{f(n)\choose 2}$, we get
$$2-2n\ge f(n)-\frac{f(n)(f(n)-1)}6\implies f(n)\ge\frac72+\frac{\sqrt{48n+1}}2\ge2\sqrt{3n}.$$
