\documentclass[12pt]{article}
\usepackage{epsfig}
\usepackage{amssymb,latexsym}

\def \proof {\par \noindent \textbf{Proof~:} }
\def \endofproof {\null\nobreak\hskip10pt plus1filll $\Box$\par}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{corollary}{Corollary}

\title{Bijective census and random generation of Eulerian planar maps with
       prescribed vertex degrees}
\author{\Large Gilles Schaeffer\\
LIX, \'Ecole Polytechnique\\ 
91128 Palaiseau Cedex, France\\
\texttt{Gilles.Schaeffer@lix.polytechnique.fr}
}
\date{Submitted: May 7, 1997; Accepted: July 17, 1997.}

\begin{document}
%
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 4 (1997),
\#R20\hfill}
\thispagestyle{empty}
%
\maketitle 
\bibliographystyle{alpha} 
\begin{center}
\textbf{Abstract} 
\begin{quote}
{\small We give a bijection between Eulerian planar maps with
prescribed vertex degrees, and some plane trees that we call
\textit{balanced Eulerian trees}. To enumerate the latter, we
introduce conjugation classes of planted plane trees. In particular
the result answers a question of Bender and Canfield in
\cite{bender-canfield-general-sphere} and allows uniform random
generation of Eulerian planar maps with restricted vertex
degrees. Using a well known correspondence between $4$-regular planar
maps with $n$ vertices and planar maps with $n$ edges we obtain an
algorithm to generate uniformly such maps with complexity $O(n)$. Our
bijection is also refined to give a combinatorial interpretation of a
parameterization of Arqu\`es (\cite{arques-tore}) of the generating
function of planar maps with respect to vertices and faces. 

Mathematical Subject Classification. Primary 05C30. }
\end{quote}
\end{center}
%
\newpage
%

A \textit{planar map} is a 2-cell decomposition of the oriented
sphere into vertices (0-cells), edges (1-cells), faces (2-cells). The
degree of a vertex is the number of edges incident to this
vertex. Loops and multiple edges are allowed. Following W.T. Tutte, we
consider here
\textit{rooted} maps i.e. maps with an oriented edge called the root.
The face which is on the right hand side of the root is called the
exterior face of the map.  Two rooted maps are \textit{isomorphic} if
there exists an orientation preserving homeomorphism of the sphere
which maps cells of one map onto cells of the same type of the second
(in particular root edge on root edge) and preserves incidences. We
shall consider maps up to these isomorphisms.

An \textit{Eulerian} planar map is a map whose vertices have even
degrees, it is \textit{$k$-regular} if all degrees are equal to
$k$. Eulerian planar maps have been studied by W.T. Tutte in
\cite{tutte-slicings} where Formula~\ref{formula} is obtained via the
study of slicings. A recursive bijective proof of this formula was
given by R. Cori in \cite{cori} but it is not constructive. More
recently, E.A. Bender and E.R. Canfield in
\cite{bender-canfield-general-sphere} gave a functional equation for
the generating function of general planar maps with respect to edges
with limitations on the vertex degrees. In the Eulerian case, their
functional equation reduces to a very simple one which suggests the
existence of a direct proof via a bijection between Eulerian maps and
pairs of some trees (see also \cite{bender-unsolved}). We give here 
such a bijection as a consequence of a construction which explains
directly all terms of the explicit formula of W.T. Tutte.

In the first section, we define balanced Eulerian trees and we
introduce conjugation classes of planted plane trees to count them.
In \cite{cori-jacquard-moi}, we applied the idea of conjugation
classes to other families of trees to give constructive proof of
several other classical formulae for different families of planar maps
with given number of edges or vertices and faces (in particular,
nonseparable maps and triangulations). This shows the existence of
a general relation between planar rooted maps and conjugation classes
of plane trees.

The next section is devoted to the bijection between trees and maps.
The construction of the bijection and that of its inverse are very simple
to describe. In particular the only non-trivial point is to prove that
among all spanning trees of an Eulerian planar map, exactly one
satisfies the Eulerian condition.

In the last section, we discuss algorithms for uniform random
generation of maps which can be deduced from the previous
bijection. Maps with limitations on the vertex degrees can be
generated via object grammars.  Maps with given vertex degrees can be
obtained directly, and in particular regular Eulerian maps with $n$
edges can be generated with complexity $O(n)$. Therefore the same
result holds for planar maps with $n$ edges, which are in one-to-one
correspondence with $4$-regular planar maps with $2n$ edges.
Previously known algorithms had complexity $O(n^2)$ in the worst case
and $O(n^{3/2})$ conjectured in the mean case (see
\cite{denise-these}).  We also show that our construction can be
refined to take into account the natural 2-coloring of faces of an
Eulerian planar map, this gives a constructive interpretation of a
parameterization due to Arqu\`es for the generating function of planar
maps with respect to numbers of vertices and faces. As a consequence
it is possible to generate randomly such maps with respect to these two
parameters.
%
%
\section{Balanced Eulerian trees}
A planted plane tree is a plane tree with a marked leaf. In drawings,
planted trees descend from their marked leaves. The degree of a vertex
is the degree in the context of graph theory, i.e. one more than the
arity in the functional representation of trees. Vertices with degree
$1$ are referred to as leaves. These trees have no labeling. The
number of such trees with $n$ edges is the famous Catalan number
$c_n={1\over n+1}{2n \choose n}$. More generally, the Lagrange
inversion formula (see \cite{bibleGJ} for instance) or encodings into
Lukaciewicz words (see \cite{lothaire} and Theorem~1) give the
following classical result:
\begin{proposition}[\cite{tutte-trees}]
The number of planted plane trees with $d_i$ vertices of degree $i+1$
for $i\geqslant 1$, $k=2+\sum(i-1)d_i$ leaves (i.e. vertices of degree
$1$) and $n=\sum d_i+k-1$ edges is:
\begin{eqnarray}
{1\over n} {n\choose
k-1,d_1,\dots,d_i,\dots}&=&{(n-1)!\over (k-1)!}\prod_{i\geqslant 1} {1\over
d_i!}.
\label{lagrange}
\end{eqnarray}
\end{proposition}

We call a tree \textit{Eulerian} if it is a planted plane tree with
$d_i$ vertices of degree $2i$ and with leaves of two colors, say black
and white, satisfying the following additional conditions: the root
leaf is black and among the $2i$ neighbors of each vertex of degree
$2i$, $i-1$ are white leaves.  Edges which are incident to a white
leaf are said to be \textit{white} whereas others are \textit{black}.

The number of planted Eulerian trees is easily deduced from
Formula~\ref{lagrange}: indeed, planted Eulerian trees are obtained
by considering planted trees with $d_i$ vertices of degree $i+1$ and
adding to each vertex of degree $i+1$ a collection of $i-1$ leaves in
all the $2i-1 \choose i$ possible ways.  In Figure~\ref{fig1} for
instance the left tree is the black skeleton of the middle tree.
\begin{figure}
\begin{center}
\epsfxsize=13cm \epsfbox {fig1.eps}
\end{center}
\caption{(i) a planted plane tree, (ii) a planted Eulerian tree, (iii) 
a balanced Eulerian tree obtained by conjugation of the previous one.}
\label{fig1}
\end{figure}
\begin{proposition}
The number of planted Eulerian trees with $d_i$ vertices of degree $2i$
for $i\geqslant 1$, $k$ black leaves and $n$ black edges is:
$${(n-1)!\over (k-1)!}\prod_{i\geqslant 1} {2i-1\choose i}^{d_i}
{1\over d_i!}.$$
\end{proposition}

Two planted Eulerian trees are \textit{conjugate} if one is obtained
 from the other by changing which black leaf is marked. On
drawings, conjugation can be viewed as a rotation of the tree. The
number of distinct planted trees in a conjugation class is therefore
usually the number of black leaves ($k$ in our notation), except of
course if there is a rotational symmetry. However rotational
symmetries of plane trees are rotation around a center: if the center
is an edge, it is a reflection and its order is $2$; if it is a vertex of
degree $2i$, it is a rotation which preserves white leaves around the
center, as well as black edges. Hence the order of the rotation must
divide $i-1$ (number of white leaves) as well as $i+1$ (number of
black edges) and it is also equal to $2$. The number of plane trees in
the class is thus $k/2$ when there is a nontrivial automorphism.
\medskip

\begin{figure}
\begin{center}
\epsfxsize=13cm \epsfbox {cyclic.eps}
\end{center}
\caption{An Eulerian tree and its cyclic word. Two ways of planting it and
the corresponding words are indicated. }
\label{cyclic}
\end{figure}

Let us now associate a cyclic word on the alphabet $\{b,w\}$ to each
Eulerian tree: when the border of an Eulerian tree is followed
counterclockwise, white and black leaves are encountered and form our
cyclic word on the alphabet $\{b,w\}$ (cf. Figure~\ref{cyclic}). When
the tree is planted, the cyclicity is broken: a black leaf is marked
and we associate with the planted tree the word ending with the
corresponding $b$. Hence conjugated trees yield conjugated words.
The number of white leaves is $\sum (i+1-2)d_i=k-2$; i.e. it is equal
to the number of black leaves minus $2$. Therefore the associated word
contains $2$ more letters $b$ than $w$.
\medskip

Hence applying a theorem of Dvoretzki and Motzkin for Lukaciewicz
words (which is stated below as Theorem~1) with $A=\{b,w\}$, $d(b)=1$
and $d(w)=-1$, there are exactly two letters $b$ such that the
conjugated word ending with one of these $b$ is of the form
$p_1bp_2b$ where $p_1$ and $p_2$ are correct bracketing words ($w$ for
opening bracket and $b$ for closing). The two corresponding leaves are
called the \textit{free} leaves of the trees and the corresponding
planted trees are called \textit{balanced} Eulerian trees.

Hence the number of balanced Eulerian trees in a conjugacy class is
$2$ except if there is a nontrivial automorphism of the underlying
Eulerian tree, in which case it is only $1$. In all cases the ratio
with the size of the conjugacy class is $2/k$. Hence from
Proposition~2:
\begin{proposition}
The number of balanced Eulerian trees with $d_i$ vertices of degree
$i+1$ for $i\geqslant 1$, $k$ leaves and $n$ edges is:
$$2{(n-1)!\over k!}\prod_{i\geqslant 1} {2i-1\choose
i}^{d_i}{1\over d_i!}.$$
\end{proposition}

The following theorem can be found in (\cite{lothaire} p.221, Thm. 11.3.6):
\begin{theorem}[Dvoretzki-Motzkin]
Let $A$ be an alphabet and $d$ a mapping from $A$ into
$\{-1\}\cup\mathbb{N}$  extended to a morphism
$d:(A^{\star},\cdot)\rightarrow(\mathbb{Z},+)$.

Let $L$ be the language of Lukaciewicz on the alphabet $A$, i.e. the
set of words $w$ satisfying $d(w)=-1$ and for all words $u$,$v$ such
that $uv=w$, $d(u)\geqslant 0$. Let $L^k$ denote the $k$th power of
$L$ for the concatenation product, i.e. the set of words $w$ which can
be written $w_1w_2\ldots w_k$ with all $w_i$ in $L$.

Let $w$ be a word of $A^{\star}$, such that $d(w)=-k$, for
some $k\geqslant 1$. Then then number of factors $u$ such that $uv=w$ and
$vu\in L^k$ is exactly $k$.
\end{theorem}

%
%
\section{Bijection between balanced Eulerian trees and Eulerian maps}
Consider a balanced Eulerian tree with $d_i$ vertices of degree $2i$.
By moving white leaves in a conterclockwise direction, glue white and
black leaves according to the bracketing systems to form new edges and
join the marked leaf to the second free black leaf to form a root edge
(Figure~\ref{fig2}). This construction yields an Eulerian planar map
with $d_i$ vertices of degree $2i$ for all $i$ and hence defines a
mapping $\phi$ from balanced Eulerian trees to Eulerian planar maps
with corresponding distribution of vertex degrees.

\begin{claim}
The mapping $\phi$ is a bijection from balanced Eulerian trees with
$d_i$ vertices of degree $2i$, $k$ black leaves and $n$ black edges
onto Eulerian planar maps with $d_i$ vertices of degree $2i$, $e=n-1$
edges and $v=n-k+1$ vertices. The inverse mapping $\psi$ is described
below.
\end{claim}

\begin{corollary}[Tutte \cite{tutte-slicings}]
The number of Eulerian planar maps with $e$ edges and $v$ vertices,
$d_i$ of which have degree $2i$, is:
\begin{eqnarray}\label{formula}
{2e!\over (e-v+2)!}\prod_{i\geqslant 1} {2i-1\choose i}^{d_i}
{1\over d_i!}.
\end{eqnarray}
\end{corollary}
\begin{figure}
\begin{center}
\epsfxsize=13cm \epsfbox{fig2.eps}
\end{center}
\caption{A balanced Eulerian tree $A$, the closure of its two 
bracketing systems and the map $\phi(A)$.}\label{fig2}
\end{figure}

We now describe the reverse mapping $\psi$ by giving an algorithm to
compute $\psi(M)$. A \textit{bridge} is an edge whose deletion
disconnects the map. The algorithm proceeds by \textit{cutting}
non-bridge edges around the map until only one face is left. The
result is then a tree which is $\psi(M)$.

A non-bridge edge incident to the exterior face is oriented by the
counterclockwise traversal around the map. Since such an edge is
encountered precisely once in such a traversal, the orientation is
well defined. We can therefore define the \textit{start} and the
\textit{end} of such an edge. Cutting an edge consists then in cutting
it and adding a white and a black leaf on the start and the end
respectively. The remaining map is the map without this edge in which
black and white leaves are considered as decorations. Since bridges
are never cut we do not cut edges that would disconnect the remaining
map.

The \textit{successor} of an end is the next plain edge around the
vertex incident to that end (i.e. turn counterclockwise and ignore
decorations until a plain edge is reached). Since the end is incident
to the exterior face of the remaining map, so is its successor.

The first step of the algorithm consists in cutting the root edge and
putting two black leaves at its end and start. The current edge is
then set to the successor of its end in the remaining map. Now the
following step is repeated until every plain edge is a bridge in the
remaining map:
\begin{itemize}
\item if the current edge $e$ is not a bridge in the remaining map, cut $e$.
\item set current edge to the successor of the end of $e$ in the
remaining map.
\end{itemize}
When the algorithm stops the remaining map is still connected, it has
no cycle and hence it is a tree with black and white leaves. Let
$\psi(M)$ be the rooted tree obtained by marking the start of the root
of $M$.
\medskip
\begin{figure}
\begin{center}
\epsfxsize=13cm \epsfbox{fig3a.eps}
\end{center}
\caption{A step of the recursion in the disconnecting case.}
\label{fig3a}
\end{figure}

\noindent\textbf{Proof of Claim~1:} By construction it is clear that 
$\psi(M)$ is a spanning tree of $M$ and that its border sequence of
white and black leaves contains two bracketing sequences separated by
the two black leaves obtained from the root edge of $M$. Hence closing
$\psi(M)$ gives back $M$, i.e.  $\phi(\psi(M))=M$. Moreover, if
$\psi(M)$ is Eulerian, it is balanced Eulerian by construction. Hence
it remains to prove that:
\begin{itemize}
\item The tree $\psi(M)$ is Eulerian, i.e. that exactly
$i-1$ white leaves are created on a vertex of degree $2i$ by $\psi$.
\item There is at most one balanced Eulerian tree $A$ such that
$\phi(A)=M$.
\end{itemize}
We will prove by induction on the number of edges of $M$ that
there is an unique balanced Eulerian tree $A$ such that $\phi(A)=M$.
In the sequel such a tree is called a tree that \textit{suits} $M$.
Checking that the recursive construction we use is equivalent to the
algorithm is straightforward: in fact the algorithm is only different
because it doesn't bother redrawing a root edge at each step.

Let $M$ be an Eulerian map with $n$ edges, let $e_0$ be its root edge
and let $e_1$ be the next edge around the exterior face.  Since an
Eulerian map cannot have a bridge, only the following three cases have
to be considered:
\begin{description}
\item[$M$ is enclosed in a loop, i.e. $e_0=e_1$:] If $M$ has only one 
edge $e_0$ then $\psi(M)$ is a vertex with degree $2$ and two black
leaves. Otherwise changing the root edge orientation yields a map $M'$
which is not enclosed anymore in a loop and will be reduced in one of
the two other cases. The successor of the end of $e_0$ in $M$ is the
same as in $M'$ since the start and the end of $e_0$ are adjacent.
Therefore $\psi(M)$ is obtained from $\psi(M')$ by exchanging the
start and the end of $e_0$. Hence it is enough to make the proof
for $M'$, i.e. in the two other cases.
\endofproof
\item[cutting $e_0$ and $e_1$ disconnects $M$:] (Figure~\ref{fig3a})
Let $M_1$ and $M_2$ be the two connected components obtained this way
and $M_1'$ and $M_2'$ the rooted Eulerian maps obtained by closing the
half edges in $M_1$ and $M_2$.  The edge $e_1$ has to belong to all
spanning trees not containing $e_0$.  Suppose now that we have a
balanced Eulerian tree $A$ that suits $M$. By definition, $A$ does not
contain $e_0$; hence it contains $e_1$.  Cutting $e_1$ yields two
Eulerian trees $A_1$ and $A_2$ which are balanced since there are no
edges in $M$ between $M_1$ and $M_2$ except $e_0$ and $e_1$. Moreover
$A_1$ and $A_2$ suit $M_1'$ and $M_2'$ respectively. Therefore they
are unique by hypothesis. Hence $A$ is unique if it exists. Conversely
an Eulerian tree suiting $M$ is immediately obtained from the two
Eulerian trees suiting $M_1'$ and $M_2'$.
\endofproof
\item[cutting $e_0$ and $e_1$ does not disconnect $M$:] 
(Figure~\ref{fig3b}) We will need the following lemma.
\begin{lemma}
Let $A$ be an Eulerian tree and $e$ an edge of $A$. Cutting $e$ yields
two planted trees $A_1$ and $A_2$.  The number of black leaves of
$A_2$ that are not closed in $A$ by white leaves of $A_2$ (i.e. free
or closed by white leaves of $A_1$) is one more than the number of
white leaves of $A_2$ closing leaves of $A_1$.
\end{lemma}
The lemma's proof requires only two sentences: The tree $A_2$ is
Eulerian, hence it has two more black leaves than white
leaves. Counting each type of leaf yields the lemma.

We now turn back to the third case and we first prove that $e_1$
cannot belong to a balanced Eulerian tree $A$ that suits $M$. Suppose
the contrary and let $A_1$ and $A_2$ be the trees which are obtained
 from $A$ by cutting $e_1$, $A_1$ being the one which contains the
start of $e_1$ and $A_2$ its end. The end of $e_0$ is the last leaf of
$A_1$ before $e_1$. Therefore when $e_1$ is reached around the tree,
the first bracketing system is closed and the second is not started
yet. Hence there cannot be any edge going from $A_1$ into $A_2$
(i.e. no white leaf of $A_1$ is closed by a black leaf of
$A_2$). According to Lemma~1, this implies that at most one edge goes
 from $A_2$ to $A_1$ (except $e_0$ and $e_1$). This third edge would
create with $e_0$ and $e_1$ a face-cycle of length $3$ which cannot
exist in an Eulerian map. Hence there is no third edge but then
cutting $e_0$ and $e_1$ disconnects the map. This gives a
contradiction. Thus $e_1$ does not belong to any suiting balanced
Eulerian tree of $M$.

Cut $e_0$ and $e_1$, delete the end of $e_0$ and start of $e_1$ and
close with a root edge the start of $e_0$ with the end of $e_1$.  The
map which is obtained is an Eulerian map $M'$ which has one edge
less. Deleting the corresponding leaves in $A$ yields a suiting
balanced Eulerian tree for $M'$ which is unique by hypothesis.  Hence
$A$ is unique. Conversely an Eulerian tree suiting $M$ is easily
constructed from the unique tree suiting $M'$.
\endofproof
\begin{figure}
\begin{center}
\epsfxsize=12cm \epsfbox{fig3b.eps}
\end{center}
\caption{A step of the recursion in the non-disconnecting case.}
\label{fig3b}
\end{figure}
\end{description}

The following additional remark gives the functional equation of
Bender and Canfield (\cite{bender-canfield-general-sphere}):
\begin{claim}
There exists a bijection between balanced Eulerian trees in which an
edge is marked and pairs of Eulerian trees with the same global vertex
degrees distribution. Hence the generating functions $E(x)$ of
balanced Eulerian trees and $M(x)$ of Eulerian planar maps with
respect to the number of edges satisfy:
$${\partial\over \partial x}(xM(x))={\partial\over \partial
x}E(x)=(A(x)/x)^2$$ 
where $A(x)$ is the generating function of planted Eulerian plane
trees with respect to number of edges (with weight $f_i$ for vertex of degree
$2i$):
$$A(x)=x+x\sum_{i\geqslant 1}{2i-1\choose i}f_iA(x)^i.$$
\end{claim}
\proof Let $A$ be a balanced Eulerian tree and $l_0$ be its marked leaf.
Mark an edge $e$ of $A$. Cutting $e$ yields two planted trees $A_1$
and $A_2$, where $A_1$ is the one which contains $l_0$ (in $A_1$,
$l_0$ is not necessarily the marked leaf). The Eulerian tree $A$
also contains a second free black leaf $l_1$ (free in the sense of the
bracketing systems).  If $l_1$ is in $A_2$, let
$\sigma(A)=(A_1,A_2)$. Otherwise $l_1$ is in $A_1$ and the cyclic
sequence composed of $\{e,l_0,l_1\}$ determines the pair we choose:
for $(l_0,l_1,e)$ we set $\sigma(A)=(A_1,A_2)$ whereas for $(l_0, e,
l_1)$ we set $\sigma(A)=(A_2,A_1)$. The mapping $\sigma$ is easily
seen to be a bijection.
\endofproof

%
%
\section{Random generation algorithms}

We consider first the problem of uniform generation of Eulerian maps
whose vertex degrees lie in a finite set $D$ of even numbers.  Planted
Eulerian trees which satisfy the corresponding constraint can be
described in the formalism of object grammars \cite{dutour-fedou} (or
in any formalism of this kind providing automated generation of trees)
and hence can be uniformly randomly generated. However because of
white leaves the number of non-terminal symbols of arity $i$ in the
grammar will be $2i-1\choose i$, despite the fact that all of them are
equivalent for the distribution. Hence the size could be kept more
reasonable by substituting one non-terminal symbol with an appropriate
multiplicity for all equivalent ones and taking the multiplicities into
account in the calculation of probabilities.  The complexity of such an
algorithm would be $O^{\star}(n^2|D|^2)$ (the $\star$ denote the fact
that grammar complexity does not take in account the size of the
numbers which are used which is exponential in this case).

This approach allows us to generate planted Eulerian trees with
respect to the number of edges or to the number of edges and
vertices. In the first case, the number of leaves of the tree is not
constrained, hence conjugation cannot be used to balance the trees and
unbalanced trees have to be rejected at the cost of a supplementary
linear factor.  However this is not a problem in the second case
where conjugation preserves uniformity.

The second problem that we address is generating a map with a given
multiset of even degrees.  In this case, conjugation can of course be
applied. Moreover, Eulerian trees can be obtained in two independent
steps: first, uniform generation of the underlying black skeleton and
second, adjunction of the white leaves. Furthermore, by encoding trees
in terms of Lukacievicz words and using Theorem~1, we see that
generation of plane trees on a given multiset of degrees is equivalent
to uniform generation of words on a given multiset of letters. This
can be achieved in complexity $O(n\log n)$ (here no $\star$ on the $O$
because we only use numbers of size $O(n)$).

Further simplifications occur in a case of particular interest. Since
complete regular trees can be generated randomly in linear time, we
have:

\begin{claim}
Uniform random generation of $k$-regular Eulerian maps with $n$ edges
can be achieved in time and space $O(n)$.
\end{claim}
\begin{corollary}
Planar maps with $n$ edges can be randomly generated with linear complexity.
\end{corollary}
The corollary follows from a well-known one-to-one correspondence between planar
maps with $n$ edges and $4$-regular maps with $2n$ edges which is
called the medial graph construction. This construction was used by
Tutte in \cite{tutte-base} to enumerate planar maps with $n$ edges.
\medskip

The $4$-regular case deserves more attention. The faces of Eulerian
maps can be bicolored and, via the medial graph correspondence, these
two colors of faces correspond to vertices and faces of planar maps.
Hence, if the distribution of colors of faces can be carried along to
our trees, the number of vertices and faces can be controlled. Denote
by positive (resp. negative) the color of the face on the left
(resp. right) hand side of the root edge of an Eulerian map $M$. There
is a one-to-one correspondence between black leaves of $\psi(M)$ and
faces of $M$ (each time a pair of brackets is closed, a face is
created). Hence the distribution of colors can be described on
balanced Eulerian trees by giving signs to black leaves: each black
leaf of $\psi(M)$ gets the sign of the face on its left hand side in
$M$. Signs are preserved by conjugation.

\begin{figure}
\begin{center}
\epsfxsize=10cm \epsfbox{fig4.eps}
\end{center}
\caption{The decomposition of $uP(u,v)$ in $uv+uP(u,v)^2+2uP(u,v)Q(u,v)$.}
\label{fig4}
\end{figure}
Now the usual decomposition of binary trees is extended to signed
planted Eulerian trees and yields the following decomposition (see
Figure~\ref{fig4}):
\begin{eqnarray*}
N(u,v)&=&u+N(u,v)^2+2N(u,v)P(u,v)\\
P(u,v)&=&v+P(u,v)^2+2P(u,v)N(u,v)
\end{eqnarray*}
where $u\cdot P(u,v)$ and $v\cdot N(u,v)$ are respectively the
generating functions of planted Eulerian trees with a positive and a
negative marked leaf with respect to the number of positive and negative
signs.

The conjugacy classes of trees split in two classes according to the
sign of the marked leaf, each class containing exactly one balanced
Eulerian tree (because the two free black leaves have opposite signs).
Hence the number of balanced Eulerian trees with $r$ positive leaves
is $1/r$ times the number of planted Eulerian trees with $r$ positive
leaves among which is the marked leaf. Therefore the generating
function $E(u,v)$ of balanced Eulerian trees with respect to number of
positive and negative signs and the generating function $M(u,v)$ of
Eulerian maps with respect to number of vertices and faces satisfy:
$${\partial M(u,v)\over \partial u}={\partial E(u,v)\over \partial u}=
P(u,v).$$
This equation for $M(u,v)$ is an alternative to Arqu\`es' expression which 
uses the same parameters $P(u,v)$ and $N(u,v)$ to prove (\cite{arques-tore}):
$$M(u,v)=P(u,v)N(u,v)(1-2P(u,v)-2N(u,v)).$$
Once again, object grammars can be applied to this decomposition:
\begin{claim}
There exists a random generation algorithm for planar maps with $i$
vertices and $j$ faces with complexity $O^{\star}(ij(i+j))$.
\end{claim}
Algorithms could also have been derived directly from Tutte's
decomposition but these decompositions require one to keep track of an
additional parameter and hence have much higher complexity.

More generally, signed trees can be used to give an equation for the
generating function of Eulerian maps with respect to number of
positive and negative faces, with weights for degrees of vertices (or
of bipartite maps with respect to the number of vertices in each part
and with weights for degrees of faces). This yields a generalisation
of Bender and Canfield's equation:
\begin{eqnarray*}
{\partial\over\partial u}E(u,v)&=&P(u,v),\quad\textrm{where}\\
N(u,v)=v&+&\sum_{i\geqslant 1}\sum_{j=1}^i{i\choose j}{i-1\choose j-1}
        Q(u,v)^jP(u,v)^{i-j}f_i,\\
P(u,v)=u&+&\sum_{i\geqslant 1}\sum_{j=1}^i{i\choose j}{i-1\choose j-1}
        P(u,v)^jQ(u,v)^{i-j}f_i.
\end{eqnarray*}
\noindent\textbf{Acknowledgements:} The author thanks Robert Cori and 
the anonymous referee for very helpful comments.
%
%
\vspace{-0.5cm}
\begin{thebibliography}{HPT64}

\bibitem[Arq87]{arques-tore}
D.~Arqu\`es.
\newblock Relations fonctionnelles et d\'enombrement des cartes point\'ees sur
  le tore.
\newblock {\em J. Comb. Theory, Ser. B}, 43:253--274, 1987.

\bibitem[BC94]{bender-canfield-general-sphere}
E.A. Bender and E.R. Canfield.
\newblock The number of degree-restricted rooted maps on the sphere.
\newblock {\em SIAM J. Discrete Math.}, 7:9--15, 1994.

\bibitem[Ben91]{bender-unsolved}
E.A. Bender.
\newblock Some unsolved problems in map enumeration.
\newblock {\em Bull. Inst. Combin. Appl.}, 3:51--56, 1991.

\bibitem[CJS]{cori-jacquard-moi}
R.~Cori, B.~Jacquard, and G.~Schaeffer.
\newblock Description trees for some families of planar maps.
\newblock accepted at FPSAC'97, Vienna.

\bibitem[Cor75]{cori}
R.~Cori.
\newblock {\em Un Code pour les Graphes Planaires et ses Applications},
  volume~27 of {\em Ast\'erisque}.
\newblock S.M.F., 1975.

\bibitem[Den94]{denise-these}
A.~Denise.
\newblock {\em M\'ethodes de G\'en\'eration Al\'eatoire d'Objets Combinatoires de
  Grande Taille et Probl\`emes d'\'Enum\'eration}.
\newblock PhD thesis, Universit\'e Bordeaux I, 1994.

\bibitem[DF]{dutour-fedou}
I.~Dutour and J.M. F\'edou.
\newblock Object grammars and random generation.
\newblock Submitted to \textit{Discrete Mathematics and Theoretical Computer
  Science.} \texttt{http:$\backslash\backslash$www.compscinet.com}.

\bibitem[GJ83]{bibleGJ}
I.P. Goulden and D.M. Jackson.
\newblock {\em Combinatorial Enumeration}.
\newblock Series in Discrete Math. Wiley-Interscience, New York, 1983.

\bibitem[HPT64]{tutte-trees}
F.~Harary, G.~Prins, and W.T. Tutte.
\newblock The number of plane trees.
\newblock {\em Indag. Math.}, 26:319--329, 1964.

\bibitem[Lot84]{lothaire}
M.~Lothaire.
\newblock {\em Combinatorics on Words}, vol.~17 of {\em Encyclopedia of
  Mathematics and its Applications}.
\newblock Cambridge Univ. Press, 1984.

\bibitem[Tut62]{tutte-slicings}
W.T. Tutte.
\newblock A census of slicings.
\newblock {\em Canad. J. Math.}, 14:708--722, 1962.

\bibitem[Tut63]{tutte-base}
W.T. Tutte.
\newblock A census of planar maps.
\newblock {\em Canad. J. Math.}, 15:249--271, 1963.

\end{thebibliography}

\end{document}