Bijective census and random generation of Eulerian planar maps with prescribed vertex

degrees

Gilles Schaeffer

LIX, École Polytechnique 91128 Palaiseau Cedex, France

    Gilles.Schaeffer@lix.polytechnique.fr

Submitted: May 7, 1997; Accepted: July 17, 1997.

Abstract

We give a bijection between Eulerian planar maps with prescribed vertex degrees, and some plane trees that we call 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 [BC94] 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ès ([Arq87]) of the generating function of planar maps with respect to vertices and faces.

Mathematical Subject Classification. Primary 05C30.

A 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 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 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 Eulerian planar map is a map whose vertices have even degrees, it is k-regular if all degrees are equal to k. Eulerian planar maps have been studied by W.T. Tutte in [Tut62] where Formula 2 is obtained via the study of slicings. A recursive bijective proof of this formula was given by R. Cori in [Cor75] but it is not constructive. More recently, E.A. Bender and E.R. Canfield in [BC94] 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 [Ben91]). 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 [CJS], 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 [Den94]). 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ès 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.

1 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} = \frac{1}{n+1} \binom{2n}{n}. More generally, the Lagrange inversion formula (see [GJ83] for instance) or encodings into Lukaciewicz words (see [Lot84] and Theorem 1) give the following classical result:

Proposition 1 ([HPT64]) The number of planted plane trees with d_{i} vertices of degree i + 1 for i ⩾ 1, k = 2 + ∑(i − 1)d_{i} leaves (i.e. vertices of degree 1) and n = ∑ d_{i} + k − 1 edges is:

\frac{1}{n}\binom{n}{k − 1, d_{1}, …, d_{i}, …} = \frac{(n − 1)!}{(k − 1)!} ∏_{i⩾1} \frac{1}{d_{i}!}.  (1)

We call a tree 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 white whereas others are black.

The number of planted Eulerian trees is easily deduced from Formula 1: 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 \binom{2i−1}{i} possible ways. In Figure 1 for instance the left tree is the black skeleton of the middle tree.

Figure 1: (i) a planted plane tree, (ii) a planted Eulerian tree, (iii) a balanced Eulerian tree obtained by conjugation of the previous one.

Proposition 2 The number of planted Eulerian trees with d_{i} vertices of degree 2i for i ⩾ 1, k black leaves and n black edges is:

\frac{(n − 1)!}{(k − 1)!} ∏_{i⩾1} \binom{2i − 1}{i}^{d_{i}} \frac{1}{d_{i}!}.

Two planted Eulerian trees are 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.

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 2). 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.

Figure 2: An Eulerian tree and its cyclic word. Two ways of planting it and the corresponding words are indicated.

The number of white leaves is ∑(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.

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_{1}bp_{2}b 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 free leaves of the trees and the corresponding planted trees are called 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:

Proposition 3 The number of balanced Eulerian trees with d_{i} vertices of degree i + 1 for i ⩾ 1, k leaves and n edges is:

2\frac{(n − 1)!}{k!} ∏_{i⩾1} \binom{2i − 1}{i}^{d_{i}} \frac{1}{d_{i}!}.

The following theorem can be found in ([Lot84] p.221, Thm. 11.3.6):

Theorem 1 (Dvoretzki-Motzkin) Let A be an alphabet and d a mapping from A into {−1} ∪ ℕ extended to a morphism d : (A^{⋆}, ·) → (ℤ, +).

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) ⩾ 0. Let L^{k} denote the kth power of L for the concatenation product, i.e. the set of words w which can be written w_{1}w_{2} … w_{k} with all w_{i} in L.

Let w be a word of A^{⋆}, such that d(w) = −k, for some k ⩾ 1. Then then number of factors u such that uv = w and vu ∈ L^{k} is exactly k.

2 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 3). This construction yields an Eulerian planar map with d_{i} vertices of degree 2i for all i and hence defines a mapping ϕ from balanced Eulerian trees to Eulerian planar maps with corresponding distribution of vertex degrees.

Claim 1 The mapping ϕ 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 ψ is described below.

Corollary 1 (Tutte [Tut62]) The number of Eulerian planar maps with e edges and v vertices, d_{i} of which have degree 2i, is:

\frac{2e!}{(e − v + 2)!} ∏_{i⩾1} \binom{2i − 1}{i}^{d_{i}} \frac{1}{d_{i}!}.  (2)

We now describe the reverse mapping ψ by giving an algorithm to compute ψ(M). A bridge is an edge whose deletion disconnects the map. The algorithm proceeds by cutting non-bridge edges around the map until only one face is left. The result is then a tree which is ψ(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 start and the end of such an edge. Cutting an edge Figure 3: A balanced Eulerian tree A, the closure of its two bracketing systems and the map ϕ(A).

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 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:

• if the current edge e is not a bridge in the remaining map, cut e.

• set current edge to the successor of the end of e in the remaining map.

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 ψ(M) be the rooted tree obtained by marking the start of the root of M.

Proof of Claim 1: By construction it is clear that ψ(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 ψ(M) gives back M, i.e. ϕ(ψ(M)) = M.

Figure 4: A step of the recursion in the disconnecting case.

Moreover, if ψ(M) is Eulerian, it is balanced Eulerian by construction. Hence it remains to prove that:

• The tree ψ(M) is Eulerian, i.e. that exactly i − 1 white leaves are created on a vertex of degree 2i by ψ.

• There is at most one balanced Eulerian tree A such that ϕ(A) = M.

We will prove by induction on the number of edges of M that there is an unique balanced Eulerian tree A such that ϕ(A) = M. In the sequel such a tree is called a tree that 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:

M is enclosed in a loop, i.e. e_{0} = e_{1}: If M has only one edge e_{0} then ψ(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 ψ(M) is obtained from ψ(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. □

cutting e_{0} and e_{1} disconnects M: (Figure 4) 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}.

□

cutting e_{0} and e_{1} does not disconnect M: (Figure 5) We will need the following lemma.

Lemma 1 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}.

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 Figure 5: A step of the recursion in the non-disconnecting case.

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′. □

The following additional remark gives the functional equation of Bender and Canfield ([BC94]):

Claim 2 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:

\frac{∂}{∂x}(xM(x)) = \frac{∂}{∂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 ∑_{i⩾1} \binom{2i − 1}{i}f_{i}A(x)^{i}.

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 σ(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 σ(A) = (A_{1}, A_{2}) whereas for (l_{0}, e, l_{1}) we set σ(A) = (A_{2}, A_{1}). The mapping σ is easily seen to be a bijection. □

3 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 [DF] (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 \binom{2i−1}{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^{⋆}(n^{2}|D|^{2}) (the ⋆ 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 ⋆ 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:

Claim 3 Uniform random generation of k-regular Eulerian maps with n edges can be achieved in time and space O(n).

Corollary 2 Planar maps with n edges can be randomly generated with linear complexity.

Figure 6: The decomposition of uP (u, v) in uv+uP (u, v)^{2}+2uP (u, v)Q(u, v).

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 [Tut63] to enumerate planar maps with n edges.

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 ψ(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 ψ(M) gets the sign of the face on its left hand side in M. Signs are preserved by conjugation.

Now the usual decomposition of binary trees is extended to signed planted Eulerian trees and yields the following decomposition (see Figure 6):

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)

where u · P (u, v) and v · 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:

\frac{∂M(u, v)}{∂u} = \frac{∂E(u, v)}{∂u} = P (u, v).

This equation for M(u, v) is an alternative to Arquès’ expression which uses the same parameters P (u, v) and N(u, v) to prove ([Arq87]):

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:

Claim 4 There exists a random generation algorithm for planar maps with i vertices and j faces with complexity O^{⋆}(ij(i + j)).

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:

\frac{∂}{∂u}E(u, v) = P (u, v), where
N(u, v) = v + ∑_{i⩾1} ∑_{j=1}^{i} \binom{i}{j}\binom{i − 1}{j − 1}Q(u, v)^{j}P (u, v)^{i−j}f_{i},

P (u, v) = u + ∑_{i⩾1} ∑_{j=1}^{i} \binom{i}{j}\binom{i − 1}{j − 1}P (u, v)^{j}Q(u, v)^{i−j}f_{i}.

Acknowledgements: The author thanks Robert Cori and the anonymous referee for very helpful comments.

References

[Arq87] D. Arquès. Relations fonctionnelles et dénombrement des cartes pointées sur le tore. J. Comb. Theory, Ser. B, 43:253–274, 1987.

[BC94] E.A. Bender and E.R. Canfield. The number of degree-restricted rooted maps on the sphere. SIAM J. Discrete Math., 7:9–15, 1994.

[Ben91] E.A. Bender. Some unsolved problems in map enumeration. Bull. Inst. Combin. Appl., 3:51–56, 1991.

[CJS] R. Cori, B. Jacquard, and G. Schaeffer. Description trees for some families of planar maps. accepted at FPSAC’97, Vienna.

[Cor75] R. Cori. Un Code pour les Graphes Planaires et ses Applications, volume 27 of Astérisque. S.M.F., 1975.

[Den94] A. Denise. Méthodes de Génération Aléatoire d’Objets Combinatoires de Grande Taille et Problèmes d’Énumération. PhD thesis, Université Bordeaux I, 1994.

[DF] I. Dutour and J.M. Fédou. Object grammars and random generation. Submitted to Discrete Mathematics and Theoretical Computer

        Science. http:\\www.compscinet.com.

[GJ83] I.P. Goulden and D.M. Jackson. Combinatorial Enumeration. Series in Discrete Math. Wiley-Interscience, New York, 1983.

[HPT64] F. Harary, G. Prins, and W.T. Tutte. The number of plane trees. Indag. Math., 26:319–329, 1964.

[Lot84] M. Lothaire. Combinatorics on Words, vol. 17 of Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 1984.

[Tut62] W.T. Tutte. A census of slicings. Canad. J. Math., 14:708–722, 1962.

[Tut63] W.T. Tutte. A census of planar maps. Canad. J. Math., 15:249– 271, 1963.