Enumeration of Planar Rooted Triangulations

Enumeration of Planar Rooted Triangulations

Jason Zhicheng Gao

School of Mathematics and Statistics, Carleton University

Algorithms Seminar

June 8, 2000

[summary by Gilles Schaeffer]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

This talk presents a joint work with I. M. Wanless and N. C. Wormald [5].

1 Introduction

A planar map is a connected graph embedded in the plane. In this talk, loops and multiple edges are forbidden. A map is rooted if one edge is oriented. The start point of this root is called the root vertex, the face on its right the root face and the face on its left the near face. If the root and near face of a planar map are the same, the root is a bridge. By convention the root is always taken so that the root face is the infinite face. The other faces are then called interior faces. The degree of a face is its number of incidences of edges (i.e., bridges count for two). A triangulation is a map whose faces all have degree three. A map is p-connected if at least p vertices must be removed to separate it into two connected components.

Euler already enumerated triangulations of polygons in the 19th century (they are Catalan), but the enumeration of triangulations as defined here started with Tutte's work in the sixties. Several families of planar rooted triangulations were in fact enumerated:

4-connected triangulations (see [8]: algebraic generating function and asymptotic are given),
3-connected triangulations (see [2, 8]: with n vertices they are (4n+1)!/(n+1)! (3n+2)!),
2-connected allowing multiple edges (see [7]: with n vertices they are 3·2ⁿ(3n)!/n! (2n+2)!),
all triangulations allowing loops and multiple edges (see [6]: algebraic generating function and asymptotic are given).

All these family of planar rooted triangulations have algebraic generating functions and asymptotic behaviors of the same form,

c_in^-5/2(1/r_i)ⁿ,

where n denotes the number of vertices. For connectivity i from 1 to 4, the values of r_i are

(3)^1/2/36, 2/27, 27/256, 4/27,

respectively. For no planar map is 6-connected, the only missing connectivity for triangulations was 5, which is the subject of the present study: it turns out that for 5-connected triangulations, the generating function is algebraic of degree 6, and the asymptotic behavior is similar, with r₅ given as a root of a certain polynomial P of degree 6 such that

r₅»0.2477.

It is amusing to remark that r₅ is not the smallest positive root the polynomial P.

The proof is based on skillful refinements of the three original ingredients of Tutte's method: root edge deletion, the quadratic method, and composition schemes.

2 Root Edge Deletion

The deletion of the root edge is maybe the simplest possible idea to decompose a map. It turns out to be very efficient in providing functional equation for generating functions of ``not-too-connected'' maps.

In general there are two cases in the root edge deletion process applied to a planar map M of a family F:

either the root edge deletion separates M into two pieces that more or less belong to F,
or it yields directly a map M' that belongs more or less to the family F. In this case, M' usually has a larger root face degree than M: the removal of the root has merged the root and near faces of M.

This decomposition can be made one-to-one, at the expense of taking the root face degree into account. It then results into functional equations for the generating function

F(x,y)=

n,k

f_n,kxⁿy^k,

where f_n,k denote the number of maps with n inner vertices and a root face of degree k.

For instance let F(x,y) be the generating function of near-triangulations, i.e., maps with all faces of degree three, except maybe the root face. Then the root edge deletion yields

F(x,y)=y²+y^-1F(x,y)²+xy^-1

(

F(x,u)-y²-yF₃(x)F(x,y)

)

where F₃(x) is the generating function of triangulations, i.e., F(x,y)=y²+F₃(x)y³+O(y⁴). Indeed in the right hand side, the three summands correspond to three cases in the decomposition of a near-triangulation M:

M is the degenerate triangulation with one edge and two vertices,
M is made of a couple of triangulations separated by a rooted triangle,
or removing the root of M directly yields a triangulation M'. In this case, M' must not be the degenerate triangulation, nor have a short diagonal cutting it into a triangulation and a near-triangulation (otherwise, replacing the root of M would create a double edge).

In order to enumerate 5-connected triangulations, it turns out to be necessary to enumerate M-type maps, i.e., maps whose interior faces have degree three or four. Their generating function

M(x,y,z)=

n,l,k

m_n,l,kxⁿy^lz^k,

where m_n,l,k denotes the number of rooted M-type maps with n triangular interior faces, l interior quadrangular faces and a root face of degree k, satisfies

M(x,y,z)=1+z²+M₃(x,y)z³+M₄(x,y)z⁴+O(z⁵)

where M₃ and M₄ denote the generating functions of M-type maps with root face of degree three and four respectively.

The root edge deletion applied to M-type maps yields, with M'=M-1,

M'=z²M²+xz^-1(M'-z²M-zM₃M')+yz^-2(M'-z²-z³M₃M-z²M₄M').

3 The Quadratic Method

The equations provided by root edge deletion have always the same flavor: they involve a principal generating function (F(y) for near-triangulations) in which the equation is quadratic, and a secondary generating function not depending on y (F₃ for near-triangulations).

The quadratic method, as used by Tutte, proceeds as follows

Write the equation in the form A²=B, where A and B are polynomials in all variables and generating functions and where B does not contain the principal generating function. E.g., for near-triangulations this gives

A=F+

1

2
(x-xyF₃-y), and B=

1

4
(x-xyF₃-y)²+xy²-y³.
In general this is possible because the equation is quadratic in F.
Show that there exists a power series Y(x) such that

A ( x,Y(x),F₃(x),F ( x,Y(x) ) ) =0.
Then

B ( x,Y(x),F₃(x) ) =

¶ B

¶ y
( x,Y(x),F₃(x) ) =0
and, provided this system is not degenerate, this proves that F₃ and Y are algebraic.

In the case of M-type maps, the situation is somewhat more involved, because of the presence of two secondary generating functions. However using a theorem of Brown on power series that are square roots [3], Bender and Canfield have dealt with a similar situation in [1]. Upon finding appropriate parametrizations to make the computation tractable with Maple, this approach yields

M₃=u³-2uv+u, and M₄=3u⁴-5u²v+u²-v²+v+2,

where u=u(x,y) and v=v(x,y) are the power series uniquely determined by

3u³-2uv+u

(1+v)³

, and y=

v-u²

(1+v)³

4 Composition Schemes and Non-Uniqueness

Root edge deletion does not work well on 4-connected triangulations or triangulations with higher connectivity, because the deletion of the root can produce maps with smaller connectivity that are hard to decompose back into maps with high connectivity. To enumerate 4-connected triangulations, Tutte introduced compositions schemes.

First remark that a triangulation is 3-connected as soon as it contains no loop and multiple edges, 4-connected if all its cycles of length three bound faces, and 5-connected if moreover it contains no 4-cycles with a vertex inside.

In the last two sections we were able to determine the generating function F₃(x) of (3-connected) triangulations. Now take a 3-connected triangulation M. Its cycles of length three are ordered by inclusion. In particular they are all inside the outer cycle of the root face; call a cycle of length three maximal if it is not inside any other one. A maximal cycle either bounds a face or contains at least one vertex in its inside. In the latter case, the maximal cycle and its inside form a triangulation.

Removing the triangulation inside each maximal cycle yields the decomposition of M into a 4-connected triangulation M' plus one triangulation per face of M' (possibly reduced to a triangle). In terms of generating functions, this yields

F₃(x)-1=

k³1

G_k x^kF₃(x)^2k+1

where G_k is the number of 4-connected triangulations with k vertices (and 2k+1 inner faces). This yields a fonctional equation of the composition type

F₃(x)=1+F₃(x)G

(

xF₃(x)²

)

which properly determines the generating function G(a) in terms of f(x)=F₃(x)². Indeed, consider the equation a=xf(x). As f(x)=1+O(x) this equation properly defines a power series x(a) and from the composition equation,

(

1-G(a)

)

²f

(

x(a)

)

(

1-G(a)

)

²a/x(a)=1.

Now as F₃(x) is algebraic, so is f(x) and there is a polynomial P(x,f) such that P(x,f(x))=0. Take x=x(a) so that

(

x(a),f

(

x(a)

)

(

x(a),a

)

=0,

and we conclude that x(a), and thus G(a), are algebraic.

The next step is to go from 4-connected triangulation to 5-connected ones. The idea is again to start with a triangulation and remove the inside of any non empty cycle of length three or four. However in general this yields an M-type map and not a triangulation.

The composition scheme has thus to be defined between 4- and 5-connected M-type maps. The same technique immediately applies to remove cycles of length three in M-type maps, but for cycle of length four, a new difficulty appear: two four cycles can overlap, making the definition of maximal four-cycles no so easy.

Finally, it turns out that a careful case study allows to classify overlapping four-cycles and work out the desired composition schemes.

5 Conclusion

Using the latter composition scheme and the results for M₃(x,y) and M₄(x,y), algebraic equations for the generating function T(x) of 5-connected triangulations can finally be derived. These equations take the form of a parametrization T(x)=F(x,s) where s has a relatively compact algebraic equation (unlike T(x)).

The asymptotic is then obtained from a careful analysis of the possible sources of singularity in the parametrization. This indirect approach seems more easily tractable than dealing with the explicit polynomial equation giving T(x).

This concludes the story for planar triangulations. As far as exact expression for generating functions are concerned, for general planar maps, there is no more than Tutte's result giving 3-connected ones. On higher genus surfaces, 2-connectivity was the limit until the very recent result of [4] for 3-connected triangulations of the projective plane.

References

[1]: Bender (Edward A.) and Canfield (E. Rodney). -- The number of degree-restricted rooted maps on the sphere. SIAM Journal on Discrete Mathematics, vol. 7, n°1, 1994, pp. 9--15.
[2]: Brown (William G.). -- Enumeration of triangulations of the disk. Proceedings of the London Mathematical Society. Third Series, vol. 14, 1964, pp. 746--768.
[3]: Brown (William G.). -- On kth roots in power series rings. Mathematische Annalen, vol. 170, 1967, pp. 327--333.
[4]: Gao (Z. C.) and Wang (J. Y.). -- Exact enumeration of rooted 3-connected triangular maps on the projective plane. -- Preprint.
[5]: Gao (Z. C.), Wanless (I. M.), and Wormald (N. C.). -- Counting 5-connected planar triangulations. -- Preprint.
[6]: Gao (Zhi-Cheng). -- The number of rooted triangular maps on a surface. Journal of Combinatorial Theory. Series B, vol. 52, n°2, 1991, pp. 236--249.
[7]: Mullin (R. C.). -- On counting rooted triangular maps. Canadian Journal of Mathematics, vol. 17, 1965, pp. 373--382.
[8]: Tutte (W. T.). -- A census of planar triangulations. Canadian Journal of Mathematics, vol. 14, 1962, pp. 21--38.

This document was translated from L^AT_EX by H^EV^EA.