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

DOI

10.2991/msam-18.2018.37How to use a DOI?

Keywords

quadrangulation; rectilinear embedding; lagrangian inversion; enumerating function

Abstract

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.

Copyright

© 2018, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Liyan Pan
AU  - Yanpei Liu
PY  - 2018/07
DA  - 2018/07
TI  - Research on the Enumerating Equation of Rectilinear Embedding- Counting Rooted Spherical Near Quadrangulations
BT  - Proceedings of the 2018 3rd International Conference on Modelling, Simulation and Applied Mathematics (MSAM 2018)
PB  - Atlantis Press
SP  - 173
EP  - 178
SN  - 1951-6851
UR  - https://doi.org/10.2991/msam-18.2018.37
DO  - 10.2991/msam-18.2018.37
ID  - Pan2018/07
ER  -