Is a regular tessellation $\{p,q\}$ always possible on some closed surface $S$?

Question

Suppose that we are given positive integers $p$, $q$, $V$, $E$, $F$, a closed surface $S$ and the Euler characteristic $\chi(S)$ of that surface. Suppose that we also know that the following relations hold: $$ qV=2E=pF\\ V-E+F=\chi(S).\tag{$\star$} $$ A regular tessellation $\{p,q\}$ is a tessellation by $p$-gons where $q$ tiles meet in every vertex. Or, using graph theory terms, an embedded $q$-regular graph whose dual is $p$-regular.

With the information above, can we say that there is a regular tessellation $\{p,q\}$ on $S$.

It is well known that if a regular tessellation $\{p,q\}$ of $S$ exists, then the relations $(\star)$ hold. So they are necessary. What I'm asking is: Are they also known to be sufficient.

---

If the answer turns out to be highly nontrivial, then I would also like to ask for a reference.

Edit 1:
An idea popped into my head, to reformulate things. We start with a $q$-regualr graph with $V$ vertices and $E=\frac{qV}2$ edges. Can we then always choose a rotation system $R$, such that we get $F=\frac{qV}p$ $p\text{-gonal}$ faces? (Remember that $p$, $q$, $V$, $E$, $F$ are given.)

The questions that must be answered in this case are:

• Can we always draw a $q$-regular graph with $V$ vertices and $E=\frac{qV}2$ edges?
• Can we always give this graph a the rotation system $R$ described above?

Does this make the problem any more feasible?

Edit 2:
As mentioned in the comments, there is an natural relation with tessellations of the hyperbolic plane and Poincaré's (polygon) Theorem.

The road to walk in this case looks, to the best of my understanding, like this:

• Consider the $\{p,q\}$ tessellation of the hyperbolic plane ($\mathbb D$).
• Try to find a simply-connected subset $P$ of this tessellation consisting of $F$ $p$-gons. Say the border of $P$ consists of $Z$ sides (each side of $P$ should be an edge of a $p$-gon).
• Find suitable side pairing for $P$. Suitable, meaning they turn $P$ into $S$.

The questions that must now be answered are:

• Can we always make a simply-connected $P$, consisting of $F$ $p$-gons such that the number of vertices and edges are "correct".
• Can we then also find suitable side pairings?

This method is the least fruitful in my opinion. Notice how the two questions to be answered here are intertwined (the number of vertices and edged is dependent on the side pairings). I already found that this is a very useful heuristic method, but it probably doen't help that much to find a genral answer. I included it here to show that I've already tried it and to point out its weak spots.

---

Edit 3:
I'm starting to think that a general proof currently might not exist. So if you can show that it holds for "a lot" of cases, I would very much like to see that. (I am contemplating making this a conjecture, so it will help to be able to say something about its likelihood.)

Answer 1

This problem was solved in

Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S. Regular tessellations of surfaces and (p,q,2)-triangle groups. Ann. of Math. (2) 116 (1982), no. 1, 113–132.

From the MathReview of the paper:

The authors consider regular tessellations of type $(p,q)$ on a surface; a generalization of the Platonic solids. The parameter $p$ is the number of edges on each face while $q$ is the valence of each vertex. The main theorem states that as long as obvious necessary conditions, based on Euler's formula, are satisfied then a regular tessellation of type $(p,q)$ exists on a surface $M$. Furthermore, the edges can be geodesics and a classification of regular tessellations of type $(p,q)$ on $M$ is given based on $\pi_1(M)$. The main technique used to prove the theorem is construction of appropriate branched coverings over surfaces with irregular patterns.

The main result of their paper is Theorem 1:

Let $M$ be a closed surface and let $p, q, V, E, F$ be positive integers such that $$ V-E+F=\chi(M)$$ and $$ pF=2E=qV$$

Then: There exists a $(p, q)$-tessellation on $M$ consisting of $F$ $p$-sided faces, $E$ edges and $V$ vertices each of valence $q$; except when $M$ is the projective plane, $(p, q) = (3,3)$, $V = F = 2$, and $E = 3$.

Note that the above conditions are also necessary for the existence of a $(p,q)$-tessellation.

An important remark: For this theorem to hold, some of the polygonal faces $\sigma$ of the tessellation are allowed to be "singular'' in the sense that some of the edges of $\sigma$ are glued to each other on the surface $M$. A simple example of a singular face is the tessellation of the 2-torus which has unique 2-dimensional rectangular face, whose edges are identified in the standard manner. In other words, the CW complex underlying the tessellation, need not be regular.

Answer 2

This is really an extended comment, rather than an answer, but it won't fit as a comment.

A little algebraic musing:

$$qV = 2E = pF$$ tells us that $$ pqV = 2pE\\ pq F = 2q E $$ so that $$ pq(V-E+F) = 2pE - pqE + 2q E = (2(p+q) - pq) E = \chi$$

So you don't really need to be given the Euler characteristic of $S$ -- you know that it's $(2(p+q) - pq) E$.

At this point the question can be divided into two parts: one where $S$ is orientable, one where it's not, for once you know an even number $\chi \le 2$, there's exactly one orientable and one nonorientable surface with that Euler characteristic.