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

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.

-
Always best to share what you've tried. –  Jagra Sep 5 '12 at 18:38
Of course. I've added an outline of my solution, and I'll post explicit code ASAP. Cheers. –  Jimeree Sep 5 '12 at 19:33
Omitting the black nodes is more than just for clarity in the case they are all of degree 2. They're not really relevant for laying out the graph. Once you've laid out your white nodes, the black ones just go in the middle of each edge. Or hang off the side for your two edge faces. –  wxffles Sep 6 '12 at 2:57
And the white nodes (of degree 3) can be simplified. For a face with $2k$ edges, you can replace $k$ white nodes with a single node of degree $k$. Then make a planar embedding of what's left with the appropriate vertex degrees. Then replace the special nodes with their associated face. The replacement might get a little tricky if faces share edges. But your {18,2,1,1,1,1} is essentially a tree. –  wxffles Sep 6 '12 at 3:07
@wxffles You're right about the black nodes - so what this amounts to (in the specific case) is finding all the graphs with $W$ trivalent nodes which satisfy condition (4). One way to do this would be to enumerate all such graphs and print the ones which satisfy (4); another would be to construct the graphs from the $r_{\infty}\left(k\right)$ as follows (taking the example of {18,2,1,1,1,1}): connect four of the nodes to themselves; connect two of the nodes together; connect these up using the other two nodes such that the "big" polygon has 18 edges. I will try these approaches today. –  Jimeree Sep 6 '12 at 11:04