Drawing dessins d'enfants (bipartite graphs subject to certain conditions)

Question

I want to write a function which constructs all possible dessins d'enfants (bipartite graphs fulfilling certain criteria, given below) from a collection of data presented in the following form:

$\begin{Bmatrix}r_{0}\left(1\right),r_{0}\left(2\right),\ldots,r_{0}\left(W\right)\\ r_{1}\left(1\right),r_{1}\left(2\right),\ldots,r_{1}\left(B\right)\\ r_{\infty}\left(1\right),r_{\infty}\left(2\right),\ldots,r_{\infty}\left(I\right) \end{Bmatrix}$

The graphs produced should be such that:

1. For every $r_{0}\left(i\right)$ there is a white node with $r_{0}\left(i\right)$ edges emanating therefrom; there are $W$ white nodes in total.
2. For every $r_{1}\left(j\right)$ there is a black node with $r_{1}\left(j\right)$ edges emanating therefrom; there are $B$ black nodes in total.
3. White nodes only join black nodes and vice versa (the graph is bipartite).
4. The graph has $I$ faces; the $k$th face is a polygon with $2r_{\infty}\left(k\right)$ sides.

(A useful simplification is that in most cases of interest, for all $i$ and $j$, $r_{0}\left(i\right)=3$ and $r_{1}\left(j\right)=2$ - I've been focusing on this specific case in my own attempted solutions).

To illustrate, the graphs at the top of page 28 in this article correspond to the data given at the top of page 25 of the same article. Taking the specific example of Ia, we see that:

• The graph has 8 white nodes, all with three connecting edges (criterion (1) above satisfied).
• The graph has 12 black nodes, all with two connecting edges (criterion (2) satisfied).
• The graph is bipartite (criterion (3) satisfied).
• The graph has six faces (one for each of the individual boxes, and one around the outside), each with eight edges (criterion (4) satisfied).

I would like to write a Mathematica function which reproduces these graphs, when the corresponding 3-vector of data is input. As a further complication, it is sometimes the case that for one set of data there are multiple dessins. For example, consider the following data:

$\begin{Bmatrix}3^{8}\\ 2^{12}\\ 18,2,1,1,1,1 \end{Bmatrix}$

(The Mathematica input for this would be something like {{3,3,3,3,3,3,3,3},{2,2,2,2,2,2,2,2,2,2,2,2},{18,2,1,1,1,1}}.) This has three dessins associated with it, drawn here. (Here, each vertex corresponds to a white node, and the author has omitted all the black nodes - he's presumably only done this for the sake of clarity). (By the way, this example also illustrates something which confused me to start off with - the "polygon" with $18\times2=32$ edges is found by going round the whole of the outside of the graph.)

I appreciate that this is not exactly a trivial problem. My approach so far has been to create a graph with $B+W$ vertices and initially no edges, making the first $B$ vertices black and the next $W$ vertices white. Then, connect each of the black vertices to two of the white vertices, such that each white vetex is connected to three black vertices (at least two of which are distinct). Check that the resulting graph is connected. Then use a cycle algorithm (such as the one here) to identify all the cycles of the graph starting at white vertices which do not backtrack, i.e. which do not go from a white vertex to a black vertex and back to a white vertex again, unless the intermediate black vertex is only connected to the initial white vertex. If those cycles have edge numbers given by the $2r_{\infty}\left(k\right)$, then draw the graph and move onto the next permutation of connections between the black vertices and white vertices. Else, just move onto the next permutation of connections between the black vertices and white vertices.

I'll post the explicit code for this algorithm ASAP (i.e. after some reworking, which will hopefully get it to do something!), but I don't think it's likely to be the most efficient way of going about the problem, and I am sure a more elegant solution is possible.

Answer 1

I've written Mathematica code which will generate a Dessin d'Enfant either in the plane or on the sphere once a Belyi map is given:

http://www.math.purdue.edu/people/bio/egoins/Dessins%20d'Enfants.html

I'm currently running an REU where we're working to implement code which will generate a Belyi map once a planar graph (actually, an augmented matrix corresponding to a planar graph) is given. We should have the code up and online within another couple of weeks.