Research on the Enumerating Equation of Rectilinear Embedding-Counting Rooted Spherical Near Quadrangulations

摘要

This paper provides quartic functional equations satisfied by the enumerating functions of rooted planar near-quadrangulations with the size, the valency of the root-face and the number of non-rooted vertices. Rooted two edge-connected planar near-quadrangulations are also counted. The quartic and the cubic functional equations are proposed for the first time, furthermore, explicit formulae for such two types of maps with above parameters are derived respectively after employing Lagrangian inversion. For two particular cases, the numbers of rooted planar trees and outerplanar quadrangulations are deduced directly. The studying results are helpful for rectilinear embedding in VLSI(Very Large Scale Integration), for the Gaussian crossing problem in graph theory, for the knot problem In topology, and for the enumeration of some other kinds of maps.