Enumeration of rooted planar halin maps

A Halin map is a kind of planar maps oriented by a tree. In this paper the rooted halin maps with the vertex partition as parameters are enumerated such that a famous result on rooted trees due to Harary. Prins, and Tutte is deduced as. a special ease. Further, by using Lagrangian inversion to obtain a number of summation free formulae dixectly, the various kinds of rooted Halin maps with up to three parameters have been counted.     

Counting non-isomorphic three-connected planar maps

A counting formula for the number of non-isomorphic planar maps with m edges was obtained by V. A. Liskovets, and non-isomorphic 2-connected planar maps were counted by Liskovets and the author. R. W. Robinson's generalization of Polya's counting theory can be applied to these formulae to count, in polynomial time, non-isomorphic planar maps satisfying various sets of restrictions. Here two sets of planar maps are counted: maps with given 2-connected components, and 3-connected maps.     

An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces.Our approach is bijective and is inspired by Lass?s proof of the Harer-Zagier formula. We first revisit Lass?s proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier?s formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q], and maps on orientable surfaces with vertex set [q]with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.     

Shuffle of parenthesis systems and baxter permutations

A formula for the number alternating Baxter permutations is given. The proof of this formula is given by constructing bijection between permutations, trees, and words. This gives also a combinatorial proof of a formula appearing in the enumerative theory of planar maps.     

带根2-连通3-正则平面地图计数

本文利用不可分离的3-正则有根平面地图的计数结果,间接地给出了2-连通 3-正则有根平面地图依边数和根面次的计数显式．     

Enumerative Properties of Rooted Circuit Maps

In 1966, Barnette introduced a set of graphs, called circuit graphs, which are obtained from 3-connected planar graphs by deleting a vertex. Circuit graphs and 3-connected planar graphs share many interesting properties which are not satisfied by general 2-connected planar graphs. Circuit graphs have nice closure properties which make them easier to deal with than 3-connected planar graphs for studying some graph-theoretic properties. In this paper, we study some enumerative properties of circuit graphs. For enumeration purpose, we define rooted circuit maps and compare the number of rooted circuit maps with those of rooted 2-connected planar maps and rooted 3-connected planar maps.     

The number of rooted circuit boundary maps

In this article, the authors discuss two kinds of new planar maps： pan-fan maps and circuit boundary maps, and provide explicit expressions about their enumerating functions with different parameters. Meanwhile, two explicit counting formulas for circuit cubic boundary maps with two parameters; the size and the valency of the root-face, are also extracted.     

Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps

Stack words stem from studies on stack-sortable permutations and represent classical combinatorial objects such as standard Young tableaux, permutations with forbidden sequences and planar maps. We extend existing enumerative results on stack words and we also obtain new results. In particular, we make a correspondence between nonseparable 3×n rectangular standard Young tableaux (or stack words where elements satisfy a ‘Towers of Hanoi’ condition) and nonseparable cubic rooted planar maps with 2n vertices enumerated by 2ⁿ(3n)!/((2n+1)!(n+1)!). Moreover, these tableaux without two consecutive integers in the same row are in bijection with nonseparable rooted planar maps with n+1 edges enumerated by 2(3n)!/((2n+1)!(n+1)!).     

BISINGULAR MAPS ON SOME SURFACES

A map is bisingular if each edge is either a loop (This paper only considersplanar loop) or an isthmus (i.e., on the boundary of the same face). This paper studies thenumber of rooted bisingular maps on the sphere and the torus, and also presents formulaefor such maps with three parameters: the root-valency, the number of isthmus, and thenumber of planar loops.     

Counting unrooted maps on the plane

A planar map is a 2-cell embedding of a connected planar graph, loops and parallel edges allowed, on the sphere. A plane map is a planar map with a distinguished outside (“infinite”) face. An unrooted map is an equivalence class of maps under orientation-preserving homeomorphism, and a rooted map is a map with a distinguished oriented edge. Previously we obtained formulae for the number of unrooted planar n-edge maps of various classes, including all maps, non-separable maps, eulerian maps and loopless maps. In this article, using the same technique we obtain closed formulae for counting unrooted plane maps of all these classes and their duals. The corresponding formulae for rooted maps are known to be all sum-free; the formulae that we obtain for unrooted maps contain only a sum over the divisors of n. We count also unrooted two-vertex plane maps.     

有根平面图计数

This is basically an expository paper on counting rooted planar maps as a part of the enumerative theory of planar maps which was founded by W.T. Tutte in the sixties.However, several new results and a certain number of simplifications and provided.     

Sharp Concentration of the Number of Submaps in Random Planar Triangulations

We show that the maximum vertex degree in a random 3-connected planar triangulation is concentrated in an interval of almost constant width. This is a slightly weaker type of result than our earlier determination of the limiting distribution of the maximum vertex degree in random planar maps and in random triangulations of a (convex) polygon. We also derive sharp concentration results on the number of vertices of given degree in random planar maps of all three types. Some sharp concentration results about general submaps in 3-connected triangulations are also given.* Research supported by NSERC and Australian Research Council Research supported by the Australian Research Council     

ENUMERATION OF ROOTED VERTEX NON-SEPARABLE PLANAR MAPS

In a rooted planar map, the rooted vertex is said to be non-separable if the vertex onthe boundary of the outer face as an induced graph is not a cut-vertex. In this paper, the author derives a functional equation satisfied by the enumeratingfuuction of rooted vertex non-separable planar maps dependent on the edge number and thenumber of the edges on the outer face boundary, finds a parametric expression of itssolution, and obtains an explicit formula for the function. Particularly, the number of rooted vertex non-separable maps only replying on theedge number and that of rooted vertex non-separable tree-like maps defined in [4] accordingto the two indices, the edge number and the number of the edges on the outer face boundary,or only one index, the edge number, are also determined.     

Transfinite mean value interpolation in general dimension

Mean value interpolation is a simple, fast, linearly precise method of smoothly interpolating a function given on the boundary of a domain. For planar domains, several properties of the interpolant were established in a recent paper by Dyken and the second author, including: sufficient conditions on the boundary to guarantee interpolation for continuous data; a formula for the normal derivative at the boundary; and the construction of a Hermite interpolant when normal derivative data is also available. In this paper we generalize these results to domains in arbitrary dimension.     

Chromatic sums of general maps on the sphere and the projective plane

In this paper, we study the chromatic sum functions of rooted general maps on the sphere and the projective plane. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of rooted loopless maps, bipartite maps and Eulerian maps are also derived. Moreover, some explicit expressions of enumerating functions are also derived.     

Klein瓶上的双奇异地图

一个地图的每条边如果不是环就是割边(即该边的两边是同一个面的边界)，则称之为双奇异地图，本文研究Klein瓶上带根双奇异地图的计数问题，得到了此类地图以边数、平面环数、手柄上本质环数和又帽上本质环数为参数的计数公式，并得到了部分计数显式。     

Chromatic sum equations for rooted cubic planar maps

This paper provides a functional equation satisfied by rooted nearly cubic planar maps. By a nearly cubic map is meant such a map that all the vertices have valency 3 with the exception of at most the root-vertex. And, as a consequence, the corresponding functional equation for rooted cubic planar maps is found.     

Counting rooted 4-regular unicursal planar maps

A map is 4-regular unicursal if all its vertices are 4-valent except two odd-valent vertices. This paper investigates the number of rooted 4-regular unicursal planar maps and presents some formulae for such maps with four parameters: the number of edges, the number of inner faces and the valencies of the two odd vertices.     

OnG 2 continuous cubic spline interpolation

In this paper the interpolation byG ² continuous planar cubic Bézier spline curves is studied. The interpolation is based upon the underlying curve points and the end tangent directions only, and could be viewed as an extension of the cubic spline interpolation to the curve case. Two boundary, and two interior points are interpolated per each spline section. It is shown that under certain conditions the interpolation problem is asymptotically solvable, and for a smooth curvef the optimal approximation order is achieved. The practical experiments demonstrate the interpolation to be very satisfactory. Supported in prat by the Ministry of Science and Technology of Slovenjia, and in part by the NSF and SF of National Educational Committee of China.