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

4connected triangulations (see [8]:
algebraic generating function and asymptotic are given),
 3connected triangulations (see [2, 8]:
with n vertices they are (4n+1)!/(n+1)! (3n+2)!),
 2connected allowing multiple edges (see [7]:
with n vertices they are 3·2^{n}(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_{i}n^{5/2}(1/r_{i})^{n},
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 6connected, the only missing
connectivity for triangulations was 5, which is the subject of the
present study: it turns out that for 5connected triangulations, the
generating function is algebraic of degree 6, and the asymptotic
behavior is similar, with r_{5} given as a root of a certain
polynomial P of degree 6 such that
r_{5}»0.2477.
It is amusing to remark that r_{5} 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 ``nottooconnected''
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 onetoone, at the expense of taking
the root face degree into account. It then results into functional
equations for the generating function
F(x,y)= 

f_{n,k}x^{n}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
neartriangulations, i.e., maps with all faces of degree three,
except maybe the root face. Then the root edge deletion yields
F(x,y)=y^{2}+y^{1}F(x,y)^{2}+xy^{1} 
( 
F(x,u)y^{2}yF_{3}(x)F(x,y) 
) 
, 
where F_{3}(x) is the generating function of triangulations, i.e.,
F(x,y)=y^{2}+F_{3}(x)y^{3}+O(y^{4}).
Indeed in the right hand side, the three summands correspond to three
cases in the decomposition of a neartriangulation 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
neartriangulation (otherwise, replacing the root of M would create
a double edge).
In order to enumerate 5connected triangulations, it turns out to be
necessary to enumerate Mtype maps, i.e., maps whose interior
faces have degree three or four. Their generating function
M(x,y,z)= 

m_{n,l,k}x^{n}y^{l}z^{k}, 
where m_{n,l,k} denotes the number of rooted Mtype maps with
n triangular interior faces, l interior quadrangular faces and a
root face of degree k, satisfies
M(x,y,z)=1+z^{2}+M_{3}(x,y)z^{3}+M_{4}(x,y)z^{4}+O(z^{5})
where M_{3} and M_{4} denote the generating functions of Mtype maps
with root face of degree three and four respectively.
The root edge deletion applied to Mtype maps yields, with M'=M1,
M'=z^{2}M^{2}+xz^{1}(M'z^{2}MzM_{3}M')+yz^{2}(M'z^{2}z^{3}M_{3}Mz^{2}M_{4}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
neartriangulations) in which the equation is quadratic, and a
secondary generating function not depending on y (F_{3} for
neartriangulations).
The quadratic method, as used by Tutte, proceeds as follows

Write the equation in the form A^{2}=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 neartriangulations this
gives
A=F+ 

(xxyF_{3}y), and B= 

(xxyF_{3}y)^{2}+xy^{2}y^{3}. 
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_{3}(x),F 
( 
x,Y(x) 
) 
) 
=0. 
 Then
B 
( 
x,Y(x),F_{3}(x) 
) 
= 

( 
x,Y(x),F_{3}(x) 
) 
=0 
and, provided this system is not degenerate, this proves that F_{3}
and Y are algebraic.
In the case of Mtype 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_{3}=u^{3}2uv+u, and M_{4}=3u^{4}5u^{2}v+u^{2}v^{2}+v+2,
where u=u(x,y) and v=v(x,y) are the power series uniquely
determined by
4 Composition Schemes and NonUniqueness
Root edge deletion does not work well on 4connected 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
4connected triangulations, Tutte introduced compositions schemes.
First remark that a triangulation is 3connected as soon as it
contains no loop and multiple edges, 4connected if all its cycles of
length three bound faces, and 5connected if moreover it contains no
4cycles with a vertex inside.
In the last two sections we were able to determine the generating
function F_{3}(x) of (3connected) triangulations. Now take a
3connected 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 4connected triangulation M' plus
one triangulation per face of M' (possibly reduced to a triangle).
In terms of generating functions, this yields
F_{3}(x)1= 

G_{k} x^{k}F_{3}(x)^{2k+1} 
where G_{k} is the number of 4connected triangulations with
k vertices (and 2k+1 inner faces). This yields a fonctional
equation of the composition type
F_{3}(x)=1+F_{3}(x)G 
( 
xF_{3}(x)^{2} 
) 
, 
which properly determines the generating function G(a) in terms of
f(x)=F_{3}(x)^{2}. 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,
( 
1G(a) 
) 
^{2}f 
( 
x(a) 
) 
= 
( 
1G(a) 
) 
^{2}a/x(a)=1. 
Now as F_{3}(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
P 
( 
x(a),f 
( 
x(a) 
) 
) 
=P 
( 
x(a),a 
) 
=0, 
and we conclude that x(a), and thus G(a), are algebraic.
The next step is to go from 4connected triangulation to 5connected
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 Mtype map and not a triangulation.
The composition scheme has thus to be defined between 4 and
5connected Mtype maps. The same technique immediately applies to
remove cycles of length three in Mtype maps, but for cycle of length
four, a new difficulty appear: two four cycles can overlap, making the
definition of maximal fourcycles no so easy.
Finally, it turns out that a careful case study allows to classify
overlapping fourcycles and work out the desired composition schemes.
5 Conclusion
Using the latter composition scheme and the results for M_{3}(x,y)
and M_{4}(x,y), algebraic equations for the generating function T(x)
of 5connected 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 3connected
ones. On higher genus surfaces, 2connectivity was the limit until the
very recent result of [4] for 3connected triangulations of
the projective plane.
References
 [1]

Bender (Edward A.) and Canfield (E. Rodney). 
The number of degreerestricted rooted maps on the sphere. SIAM
Journal on Discrete Mathematics, vol. 7, n°1, 1994,
pp. 915.
 [2]

Brown (William G.). 
Enumeration of triangulations of the disk. Proceedings of the
London Mathematical Society. Third Series, vol. 14, 1964,
pp. 746768.
 [3]

Brown (William G.). 
On kth roots in power series rings. Mathematische Annalen,
vol. 170, 1967, pp. 327333.
 [4]

Gao (Z. C.) and Wang (J. Y.). 
Exact enumeration of rooted 3connected triangular maps on the
projective plane. 
Preprint.
 [5]

Gao (Z. C.), Wanless (I. M.), and Wormald (N. C.). 
Counting 5connected planar triangulations. 
Preprint.
 [6]

Gao (ZhiCheng). 
The number of rooted triangular maps on a surface. Journal of
Combinatorial Theory. Series B, vol. 52, n°2, 1991,
pp. 236249.
 [7]

Mullin (R. C.). 
On counting rooted triangular maps. Canadian Journal of
Mathematics, vol. 17, 1965, pp. 373382.
 [8]

Tutte (W. T.). 
A census of planar triangulations. Canadian Journal of
Mathematics, vol. 14, 1962, pp. 2138.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.