It is an old result that any (finite) graph can be embedded in an orientable surface. (The result can be found, for instance in White 1984, in which he give an algorithm, calling it the Edmonds algorithm and giving a date of 1960, (see Edmonds 1960).)
In 1879 Felix Klein (see Klein’s dessins d’enfants) in his paper “Über die Transformationen elfter Ordnung der elliptischen Funktionen” (“On the transformations of order eleven of elliptic functions” ) classified some Riemann surfaces of a certain ramification type by associating to covers of the surface with certain monodromy group their ”dessin’s denfants” which he called ”Linienzüge”.
The modern perception of dessin’s d’enfants begins with Grothendieck, who showed how to describe, categorically, the geometric structure corresponding to such embedded graphs, namely by the action of a certain ‘cartographic group’ on sets. His motivation was the way in which this shed light on the structure of Riemann surfaces, and through that to the absolute Galois group $G$ of the rational numbers. The technical vehicle explicating this relation is Belyi’s theorem from which follows that $G$ has a faithful action on Grothendieck’s dessin’s d’enfants.
A dessin d’enfant (French for a ”child’s drawing”, plural ”dessins d’enfants”, ”children’s drawings”) is a type of graph drawing used to study Riemann surfaces and to provide combinatorial invariants? for the action of the absolute Galois group of the rational numbers.
”Intuitively, a dessin d’enfant is simply a graph, with its vertices colored alternating black and white, embedded? onto an oriented surface? that, in many cases, is simply a plane. For the coloring to exist, the graph must be bipartite?. The faces of the embedding must be topological disks. The surface and the embedding may be described combinatorially using a rotation system?, a cyclic order of the edges surrounding each vertex of the graph that describes the order in which the edges would be crossed by a path that travels clockwise on the surface in a small loop around the vertex. Any dessin can provide the surface it is embedded on with a structure as a Riemann surface. It natural to ask which Riemann surfaces arise in this way. The answer is provided by Belyi's theorem?, which states that these are precisely those that can be defined over the field of algebraic numbers (when considered as algebraic curves). The absolute Galois group transforms these particular curves into each other, and thereby also transforms the underlying dessins.” (wikipedia)
The original development does not, however, explicitly use bipartite graphs, rather it used a form of 1-complex, embedded in a surface (see below). The use of bipartite graphs simplifies the exposition.
A dessin d’enfant is a bipartite connected graph $G$ which is embedded into an orientable closed topological surface $X$, such that it ﬁlls the surface, i.e. $X \setminus G$ is a union of open cells. Two dessins d’enfants $(X_1 , G_1 )$ and $(X_2 , G_2 )$ are called equivalent if there exists a homeomorphism $f : X_1 \to X_2$ such that $f (G_1 ) = G_2$ .
An example for a bipartite (connected) graph is a tree.
It is well known that the bipartite graph $K_{3,3}$ is non-planar, so does not embed in the 2-sphere, but will embed in the torus, in such a way that its complement is a disjoint union of discs.
The original work was stated in terms of objects called cellular maps?, and the category of these cellular maps and isotopy classes of morphisms between them was shown to correspond to a category of finite $\mathbb{G}$-sets where $\mathbb{G} is a group called the cartographic group?, which has a simple presentation in terms of operations of a geometric / combinatorial nature. )
(from the Esquisse d'un programme describing the idea as seen by Grothendieck:)
”My interest in topological surfaces began to appear in 1974, when I proposed to Yves Ladegaillerie the theme of the isotopic study of embeddings of a topological 1-complex into a compact surface. Over the two following years, this study led him to a remarkable isotopy theorem, giving a complete algebraic description of the isotopy classes of embeddings of such 1-complexes, or compact surfaces with boundary, in a compact oriented surface, in terms of certain very simple combinatorial invariants, and the fundamental groups of the protagonists. This theorem, which should be easily generalisable to embeddings of any compact space (triangulable to simplify) in a compact oriented surface, gives as easy corollaries several deep classical results in the theory of surfaces, and in particular Baer’s isotopy theorem.
In the work of Ladegaillerie there is also a purely algebraic description, in terms of fundamental groups, of the ”isotopic” category of compact surfaces X , equipped with a topological 1-complex K embedded in X . This description, which had the misfortune to run counter to ”today’s taste” and because of this appears to be unpublishable, nevertheless served (and still serves) as a precious guide in my later reflections, particularly in the context of absolute algebraic geometry in characteristic zero.
Fairly elementary sources for background material include:
This gives the Edmonds algorithm for the embedding. the original source for that is:
References on the deeper theory as developed by Grothendieck and his students, and including summaries of subsequent work, include:
L. Schneps, ed., 1994, The Grothendieck theory of dessins d’enfants , volume 200 of London Mathematical Society Lecture Note Series , Cam- bridge University Press, Cambridge, papers from the Conference on Dessins d’Enfant held in Luminy, April 19–24, 1993
Marco Robalo, Galois Theory towards Dessins d’Enfants (pdf)
F. Herrlich, G. Schmithüsen: Dessins d’enfants and Origami curves
The original work on the elementary theory was contained in
Christine Voisin?, Jean Malgoire?, Cartes cellulaires, Cahiers Mathématiques, 12, Montpellier, 1977.
Christine Voisin?, Jean Malgoire?, Factorisation de Stein topologique, découpe, Cahiers Mathématiques, 15, Montpellier, 1979.
Christine Voisin?, Jean Malgoire?, Cartes topologiques infinies et revetemnts ramifies de la sphere, Cahiers Mathématiques, 19, Montpellier, 1980.
The Wikipedia page on this is:
References on the history of dessins d’enfants