\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{tikz} \usetikzlibrary{arrows,decorations.markings} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{amsmath, amssymb, amsthm} \usepackage{cleveref} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \renewcommand{\theenumi}{(\roman{enumi})} \renewcommand{\labelenumi}{\theenumi} \newcommand{\abs}[1]{\left\vert#1\right\vert} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\br}[1]{\left(#1\right)} \newcommand{\torus}[1]{\mathbb{S}_{#1}} \newcommand{\Sg}{\mathbb{S}_g} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\opa}[1]{\delta_#1} \newcommand{\opb}[2]{\left(\delta_#1+\delta_#2\right)} \DeclareMathOperator{\fw}{fw} \DeclareMathOperator{\ew}{ew} \newcommand{\class}[1]{\mathcal{#1}} \newcommand{\edge}[1]{\overline{#1}} \newcommand{\vertex}[1]{#1} \newcommand{\deriv}[1]{\frac{\partial}{\partial #1}} \newcommand{\derivf}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\derivn}[2]{\frac{\partial^{#2}}{\partial #1^{#2}}} \newcommand{\X}{\br{\frac{27}{256}-x}} \newcommand{\Y}{\br{\frac{3}{2^{8/3}}-y}} \DeclareMathOperator{\tr}{tr} \newcommand{\triangt}{\hat{S}} \def\triangs{S} \def\triangm{M} \def\three{D} \def\two{B} \def\one{C} \def\general{G} \def\all{m} \def\network{N} \def\quasis{P} \def\quasit{Q} \def\main{M} \def\error{E} \def\dd#1{\,\mathrm{d}{#1}} \def\oy{\overline{y}} \def\oz{\overline{z}} \def\Gimenez{Gim{\'e}nez\;} \definecolor{gray}{gray}{0.9} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{coro}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{remark}[thm]{Remark} \theoremstyle{definition} \newtheorem{definition}[thm]{Definition} \crefname{thm}{theorem}{theorems} \crefname{prop}{proposition}{propositions} \crefname{coro}{corollary}{corollaries} \crefname{lem}{lemma}{lemmas} \crefname{definition}{definition}{definitions} \pagestyle{plain} \newtheoremstyle{claim} {} {} {\itshape} {} {\bf} {.} {.5em} {} \theoremstyle{claim} \newtheorem{claim}{Claim} \crefname{claim}{claim}{claims} \title{Cubic graphs and related triangulations \\on orientable surfaces\thanks{An extended abstract of this paper has been published in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), 603--610.}} \author{Wenjie Fang\thanks{Partially funded by \textit{Agence Nationale de la Recherche}, grant ANR 12-JS02-001-01 ``Cartaplus'' during doctoral study at University Paris Diderot} \thanks{Supported by Austrian Science Fund (FWF): P2309-N35} \, Mihyun Kang\textsuperscript{\fnsymbol{footnote}}\thanks{Supported by Austrian Science Fund (FWF): P27290 and W1230 II} \, Michael Mo{\ss}hammer\textsuperscript{\fnsymbol{footnote}} Philipp Spr{\" u}ssel\textsuperscript{\fnsymbol{footnote}}\\ \small Institute of Discrete Mathematics\\[-0.8ex] \small Graz University of Technology\\[-0.8ex] \small Graz, Austria\\ \small\tt \{fang,kang,mosshammer,spruessel\}@math.tugraz.at } \date{\dateline{Mar 4 2016}{Jan 23, 2018}\\ \small Mathematics Subject Classifications: 05A16, 05C10, 05C30} \begin{document} \maketitle \begin{abstract} Let $\mathbb{S}_g$ be the orientable surface of genus $g$ for a fixed non-negative integer $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on $\mathbb{S}_g$ with $2n$ vertices is asymptotically $c_g n^{5/2(g-1)-1}\gamma^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally, for $g\ge1$, we prove that a typical cubic multigraph embeddable on $\mathbb{S}_g$ has exactly one non-planar component. \end{abstract} \bigskip\noindent \textbf{Keywords:} Cubic graphs; graphs on surfaces; triangulations; asymptotic enumeration; analytic combinatorics. \section{Introduction} Determining the numbers of maps and graphs \emph{embeddable} on surfaces have been one of the main objectives of enumerative combinatorics for the last 50 years. Starting from the enumeration of \emph{planar} maps by Tutte \cite{tutte1963-planar-maps} various types of maps on the sphere were counted, e.g.\ planar \emph{cubic} maps by Gao and Wormald \cite{MR1980342}. Furthermore, Tutte's methods were generalised to enumerate maps on surfaces of higher genus \cite{BENDER1986244,Bender1993-maps,Bender1988370}. An important subclass of maps are \emph{triangulations}. Brown \cite{triang-disk} determined the number of triangulations of a disc, and Tutte enumerated planar triangulations \cite{tutte1962-planar-triangulations}. Triangulations on other surfaces have been considered as well. Gao enumerated $2$-connected triangulations on the projective plane \cite{Gao1991-2-connected-projective} as well as connected \cite{Gao1991-conn-triang}, $2$-connected \cite{Gao1992-2-connected-surface} and $3$-connected \cite{Gao1993-pattern} triangulations on surfaces of arbitrary genus. Frieze \cite{seminaronrg} was arguably the first to ask about properties of random planar \emph{graphs}. McDiarmid, Steger, and Welsh \cite{mcdiarmid2005} showed the existence of an exponential growth constant for the number of vertex-labelled planar graphs with $n$ vertices. This growth constant and the asymptotic number of planar graphs were determined by \Gimenez and Noy \cite{gimenez2009}, while the corresponding results for the higher genus case were derived by Chapuy, Fusy, Gim{\'e}nez, Mohar and Noy \cite{Chapuy2011-enumeration-graphs-on-surfaces} and independently by Bender and Gao \cite{bendergao}. Since then various other classes of planar graphs were counted \cite{bender,Bodirsky08,bodirsky2007-cubic-graphs,rgraphs,kang2012,ks,osthus}. An interesting subclass of planar graphs is the class of \emph{cubic} planar graphs, which have been counted by Bodirsky, Kang, L\"offler and McDiarmid \cite{bodirsky2007-cubic-graphs}. Cubic planar graphs occur as substructures of sparse planar graphs and have thus been one of the essential ingredients in the study of sparse random planar graphs \cite{kang2012}. For surfaces of higher genus, the number of embeddable cubic graphs has not been studied. Throughout the paper, let $g$ be a fixed non-negative integer and let $\Sg$ be the orientable\footnote{We believe that one can also prove the main results for multigraphs embeddable on non-orientable surfaces, but with considerably more effort and case distinctions.} surface of genus $g$. In this paper, we study cubic graphs embeddable on $\Sg$, in particular their asymptotic number. Similar to the case of planar graphs, cubic graphs embeddable on $\Sg$ appear as essential substructures of sparse graphs embeddable on $\Sg$. Therefore, the results of this paper pave the way to the study of sparse random graphs embeddable on $\Sg$ \cite{kms17}. \subsection{Main results} The main contributions of this paper are fourfold. We determine the asymptotic number of cubic multigraphs embeddable on $\Sg$. We also determine the asymptotic number of \em{weighted} cubic multigraphs and cubic \em{simple} graphs embeddable on $\Sg$. Finally we prove that almost all (multi)graphs from either of the three classes have exactly one non-planar component. The first main result provides the exact asymptotic expression of the number of cubic multigraphs embeddable on $\Sg$. \begin{thm}\label{main1} The number $m_g(n)$ of vertex-labelled cubic multigraphs embeddable on $\Sg$ with $2n$ vertices is given by \begin{align*} m_g(n)&=\br{1+O\br{n^{-1/4}}}d_gn^{5g/2-7/2}\gamma_1^{2n}(2n)!\, , \end{align*} where $\gamma_1$ is an algebraic constant independent of the genus $g$ and $d_g$ is a constant depending only on $g$. The first digits of $\gamma_1$ are $3.986$. \end{thm} Our next main result concerns multigraphs weighted by the so-called \emph{compensation factor} introduced by Janson, Knuth, \L{}uczak and Pittel \cite{jansonea}. This factor is defined as the number of ways to orient and order all edges of the multigraph divided by $2^rr!$, which is equal to the number of such oriented orderings if all edges were distinguishable. For example, a double edge results in a factor $\frac{1}{2}$ and simple graphs are the only multigraphs with compensation factor one. \begin{thm}\label{main2} The number $w_g(n)$ of vertex-labelled cubic multigraphs embeddable on $\Sg$ with $2n$ vertices \em{weighted by their compensation factor} is given by \begin{align*} w_g(n)&=\br{1+O\br{n^{-1/4}}}e_g n^{5g/2-7/2}\gamma_2^{2n}(2n)!\,, \end{align*} where $\gamma_2=\frac{79^{3/4}}{54^{1/2}}$ and $e_g$ is a constant depending only on the genus $g$. The first digits of $\gamma_2$ are $3.606$ \end{thm} \Cref{main2} can be used to derive the asymptotic number and structural properties of graphs embeddable on $\Sg$ \cite{kms17}. \emph{Planar} cubic multigraphs weighted by the compensation factor were counted by Kang and \L{}uczak \cite{kang2012}. The discrepancy to their exponential growth constant $\gamma\approx 3.38$ is due to incorrect initial conditions in \cite{kang2012}, as pointed out by Noy, Ravelomanana and Ru{\'e} \cite{Noy2012-probability-of-planarity}. While the explicit value of the correct exponential growth constant $\gamma$ was not determined in \cite{Noy2012-probability-of-planarity}, the implicit equations given there yield the same exponential growth constant $\gamma_2$ as in \Cref{main2}. Our methods also allow us to count cubic \emph{simple} graphs (graphs without loops and multi-edges) embeddable on $\Sg$. \begin{thm}\label{main3} The number $s_g(n)$ of vertex-labelled cubic \em{simple} graphs embeddable on $\Sg$ with $2n$ vertices is given by \begin{align*} s_g(n)&=\br{1+O\br{n^{-1/4}}}f_g n^{5g/2-7/2}\gamma_3^{2n}(2n)!\,, \end{align*} where $\gamma_3$ is an algebraic constant independent of the genus $g$ and $f_g$ is a constant depending only on $g$. The first digits of $\gamma_3$ are $3.133$. \end{thm} The exponential growth constant $\gamma_3$ coincides with the growth constant calculated for vertex-labelled cubic simple planar graphs by Bodirsky, Kang, L\"offler and McDiarmid \cite{bodirsky2007-cubic-graphs}. The final result describes the structure of cubic multigraphs embeddable on $\Sg$. \begin{thm}\label{main4} Let $g\ge 1$ and let $G$ be a graph chosen uniformly at random from the class of vertex-labelled cubic multigraphs, cubic weighted multigraphs, or cubic simple graphs embeddable on $\Sg$ with $n$ vertices, respectively. Then with probability $1-O(n^{-2})$, $G$ has one component that is embeddable on $\Sg$, but not on $\torus{g-1}$, while all other components of $G$ are planar. \end{thm} \subsection{Proof techniques} To derive our results we will use topological manipulations of surfaces called \emph{surgeries}, constructive decomposition of graphs along connectivity, and singularity analysis of generating functions. More precisely, in order to enumerate cubic multigraphs we apply constructive decompositions along connectivity. The basic building blocks in the decomposition are $3$-connected cubic graphs, which we will then relate to their corresponding cubic \emph{maps}. Note that, due to Whitney's Theorem \cite{whitney}, $3$-connected \emph{planar} graphs have a unique embedding on the sphere. Therefore, we can directly relate $3$-connected planar graphs to the corresponding maps. For surfaces of positive genus, however, embeddings of $3$-connected graphs are \emph{not} unique. Following an idea from \cite{Chapuy2011-enumeration-graphs-on-surfaces}, we circumvent this problem by using the concept of the \emph{facewidth} of a graph and by applying results of Robertson and Vitray \cite{robertson1990-representativity} which relate $3$-connected graphs and maps. Counting $3$-connected cubic maps on $\Sg$ is a challenging task. We shall use the dual of cubic maps, triangulations, in order to overcome this challenge. In fact, Gao \cite{Gao1991-2-connected-projective, Gao1992-2-connected-surface, Gao1993-pattern} enumerated triangulations on $\Sg$ with various restrictions on the existence of loops and multi-edges. However, it turns out that the duals of $3$-connected cubic maps on $\Sg$ have very specific constraints that have not been considered by Gao. In this paper we therefore investigate such triangulations by relating them to simple triangulations counted by Gao \cite{Gao1992-2-connected-surface} (see \Cref{simplerefined,essentialsimple,threeconn-dual}). We strengthen Gao's result and derive very precise singular expansions of generating functions. These expansions are obtained from recursive formulas for the generating functions, which we derive by applying surgeries to the surfaces on which the respective triangulations are embedded. This enables us to apply singularity analysis to the generating functions of these triangulations, as well as to the generating functions of all other classes of maps and graphs considered in this paper. This paper is organised as follows. In \Cref{sec:prelims} we introduce some basic notions and notations. In \Cref{maps} we enumerate the triangulations that are duals of $3$-connected cubic maps and in \Cref{graphs} we prove the main results (\Cref{main1,main2,main3,main4}) after giving a constructive decomposition along connectivity. Our strengthening of Gao's results and proofs, as well as other proofs for similar theorems from \Cref{maps}, are given in the appendix. \section{Preliminaries}\label{sec:prelims} A graph $G$ is \emph{simple} if it does not contain loops or multi-edges. If in a multigraph there are more than two edges connecting the same pair of vertices, we call each pair of those edges a \emph{double edge}. Therefore, every multi-edge consisting of $r$ edges between the same two vertices contains $\binom{r}{2}$ double edges. If $e$ is a loop and incident to a vertex $v$, we say that $v$ is the \emph{base} of $e$. Similarly, we say that $e$ is \emph{based at} its base. An edge that is neither a loop nor part of a double edge is a \emph{single edge}. An edge $e$ of a connected multigraph $G$ is called a \emph{bridge} if deleting $e$ disconnects $G$. A multigraph is called \emph{cubic} if each vertex has degree three. We adopt the convention that a loop counts as two in the degree of its base. By $\Phi$ we denote the cubic multigraph with two distinguished vertices $u,v$ and three edges between $u$ and $v$ (i.e.\ a triple edge). Given a connected cubic multigraph $G$, let $k$ and $l$ denote the number of double edges and loops of $G$, respectively. We define the \emph{weight} of $G$ to be \begin{equation*} W(G) = \begin{cases} \frac16 & \text{if } G = \Phi,\\ 2^{-(k+l)} & \text{otherwise}. \end{cases} \end{equation*} If $G$ is not connected, we define $W(G)$ as the product of weights of its components. For cubic multigraphs, this weight coincides with the compensation factor introduced in \cite{jansonea}. Throughout this paper, when we refer to a \emph{weighted cubic multigraph} $G$, the weight in consideration will always be $W(G)$. \begin{definition} An \emph{embedding} of a multigraph $G$ on $\Sg$ is a drawing of $G$ on $\Sg$ without crossing edges. We consider $G$ as a subset of $\Sg$, and therefore $\Sg\setminus G$ consists of connected components called \emph{faces}. An embedding where additionally all faces are homeomorphic to open discs, or equivalently, where all faces are simply connected, is called a \emph{$2$-cell embedding}. Multigraphs that have an embedding are called \emph{embeddable} on $\Sg$ and multigraphs that have a $2$-cell embedding are called \emph{strongly embeddable}. A $2$-cell embedding of a strongly embeddable multigraph is also called \emph{map}. A \emph{triangulation} is a map where each face is bounded by a triangle. These triangles might be degenerated, i.e., being three loops with the same base, or a double edge and a loop based at one of the end vertices of the double edge, or a loop and an edge from the base of the loop to a vertex of degree one. If $S$ is the disjoint union of $\torus{g_1},\ldots,\torus{g_r}$ for non-negative integers $g_1,\ldots,g_r$ and $M_i$ is a $2$-cell embedding of a graph $G_i$ on $\torus{g_i}$ for each $i=1,\ldots,r$, then the induced function $N:(G_1\cup\cdots\cup G_n)\to S$ is called a \emph{map} on $S$. Triangulations on $S$ are defined analogously. We denote by $V(M)$, $E(M)$, and $F(M)$ the set of all vertices, edges, and faces of an embedding $M$, respectively. We call a set $E'\subseteq E(M)$ \emph{separating}, if the map $M'=(V(M),E')$ has at least two faces, i.e.~if $M'$ separates the surface. \end{definition} From results of Mohar and Thomassen \cite{mohar-thomassen} we obtain some initial properties of embeddable graphs. \begin{prop}\cite{mohar-thomassen}\label{strongemb} Let $G$ be a multigraph. \begin{enumerate} \item\label{strong:minimal} If $G$ is connected and $g$ is minimal such that $G$ is embeddable on $\Sg$, then every embedding of $G$ on $\Sg$ is a $2$-cell embedding. In particular, $G$ is strongly embeddable on $\Sg$. \item\label{strong:emb} $G$ is embeddable on $\Sg$ if and only if each connected component $C_i$ of $G$ is strongly embeddable on a surface $\torus{g_i}$ such that $\sum_i g_i\le g$. \end{enumerate} \end{prop} Let $M$ be a map on a surface $\mathbb{S}$. We construct the \emph{dual map} of $M$ by first putting a vertex in each face of $M$, then for each edge $e$ in $M$, we draw an edge between the two (possibly coincident) vertices inside the faces on both side of $e$ while crossing $e$ exactly once. The newly drawn edges should only intersect at their end points. Note that the dual map has multi-edges if two faces of the original (\emph{primal}) map have more than one edge in common. It is well known that the dual of a map is again a map, see e.g.~\cite{mohar-thomassen}. For each vertex $v\in V(M)$ of a map $M$, the edges and faces incident to $v$ have a canonical cyclic order $e_0,f_0,e_1,f_1,\ldots,e_{d-1},f_{d-1}$ by the way they are arranged around $v$ (in counterclockwise direction). Note that faces can appear multiple times here and that a loop based at $v$ will appear twice in this sequence. To avoid ambiguities, we distinguish the two ends of the loop in this sequence (e.g. by using half-edges or by orienting each loop). A triple $(v,e_i,e_{(i+1)\bmod d})$ of a vertex $v$ and two consecutive edges $e_i,e_{i+1\bmod d}$ in the cyclic sequence is called a \emph{corner} (at $v$). We also say that $(v,e_i,e_{(i+1)\bmod d})$ is a corner \emph{of the face $f_i$}. When we enumerate maps, we always work with maps with one distinguished corner, called the \emph{root} of the map. If $(v,e_i,e_{i+1})$ is the root corner, we will call $v$ the \emph{root vertex}, $e_i$ the \emph{root edge}, and $f_i$ the \emph{root face}. \subsection{Generating functions and singularity analysis}\label{section:singularity} We will use generating functions to enumerate the various classes of maps, graphs and multigraphs we consider. Unless stated otherwise, the formal variables $x$ and $y$ will always mark vertices and edges respectively. Generating functions for classes of \emph{maps} will be \emph{ordinary} unless stated otherwise. Generating functions for \emph{multigraphs} will be \emph{exponential} in $x$, because we always consider \emph{vertex-labelled} multigraphs. If $\class{A}$ is a class of maps, we write $\class{A}(m)$ for the subclass of $\class{A}$ containing all maps with exactly $m$ edges. The generating function $\sum_m |\class{A}(m)|y^m$ will be denoted by $A(y)$. If $\class{B}$ is a class of multigraphs, we write $\class{B}(n)$ for the subclass of $\class{B}$ containing all multigraphs with exactly $n$ vertices. The generating function $\sum_n \frac{|\class{B}(n)|}{n!}x^n$ will be denoted by $B(x)$. For an ordinary generating function $F(z)=\sum_n f_nz^n$, we use the notation $[z^n]F(z):=f_n$. For an exponential generating function $G(z)=\sum\frac{g_n}{n!}z^n$, we write $[z^n]G(z):=\frac{g_n}{n!}$. If two generating functions $F(z), G(z)$ satisfy $0 \leq [z^n]F(z) \leq [z^n] G(z)$ for all $n$, we say that $F$ is \emph{coefficient-wise smaller} than $G$, denoted by $F \preceq G$. The singularities of $F(z)$ with the smallest modulus are called \emph{dominant singularities} of $F(z)$. Because every generating function we consider in this paper always has non-negative coefficients $[z^n]F(z)$, there is a dominant singularity located on the positive real axis by Pringsheim's Theorem \cite[pp. 214 ff.]{titchmarsh1939theory}. We denote this dominant singularity by $\rho_F$. If an arbitrary function $F:\C\to\C$ has a unique singularity with smallest modulus and this singularity lies on the positive real axis, then we also denote it by $\rho_F$. The function $F$ converges on the open disc of radius $\rho_F$ and thus corresponds to a holomorphic function on this disc. In many cases, this function can be holomorphically extended to a larger domain. Given $\rho,R\in\R$ with $0<\rho \theta \} \end{equation*} is called a \emph{$\Delta$-domain}. Here, $\arg(z)$ denotes the \emph{argument} of a complex number, that is $\arg(0) := 0$ and $\arg(re^{it}) := t$ for $r>0$ and $t\in(-\pi,\pi]$. We say that $F$ is \emph{$\Delta$-analytic} if it is holomorphically extendable to some $\Delta$-domain $\Delta(\rho_F,R,\theta)$. A function $F$ is \emph{subdominant} to a function $G$ if either $\rho_F>\rho_G$ or $\rho_F=\rho_G$ and $\lim_{z\to \rho_G}\frac{F(z)}{G(z)}=0$. In the latter case, if both $F$ and $G$ are $\Delta$-analytic, then in the above limit, $z$ is taken from some fixed $\Delta$-domain to which both $F$ and $G$ are holomorphically extendable. If $F$ is subdominant to $G$, we also write $F(z)=o(G(z))$. Analogously we write $F(z)=O(G(z))$ if either $\rho_F>\rho_G$ or $\rho_F=\rho_G$ and $\limsup_{z\to \rho_G}\frac{|F(z)|}{|G(z)|}<\infty$. Given a function $F(z)$ with a dominant singularity $\rho_F$, we say that a function $G(z)=c\br{1-\rho_F^{-1}z}^{-\alpha}$ with $\alpha\in\R\setminus\Z_{\le 0},c\in\R\setminus\{0\}$ or $G(z)=c\log\br{1-\rho_F^{-1}z}$ is the \emph{dominant term} of $F$ if there is a decomposition \begin{equation*} F(z) = P(z) + G(z) + o(G(z)), \end{equation*} where $P(z)$ is a polynomial. The dominant term, if it exists, is uniquely defined and $\Delta$-analytic. If $G(z)=c(1-\rho_F^{-1}z)^{-\alpha}$, the exponent $-\alpha$ is called the \emph{dominant exponent} of $F$. If $G(z)=c\log\br{1-\rho_F^{-1}z}$, then we say that $F$ has the dominant exponent $0$. The number of edges in cubic multigraphs and triangulations is always a multiple of three. In terms of generating functions, this is reflected by the existence of three different dominant singularities, all of which differ only by a third root of unity. The corresponding dominant terms will also be the same up to a third root of unity. Analogously, the number of vertices in cubic multigraphs is always even, resulting in two dominant singularities $\rho_F$ and $-\rho_F$. Again, the dominant terms differ only by a factor of $-1$. In either case, the terms for the coefficients coming from the different dominant singularities will also differ only by the corresponding root of unity. Therefore, we will state our results only for the singularity $\rho_F$. With a slight abuse of notation, we will also refer to $\rho_F$ as \emph{the} dominant singularity. Singularity analysis allows us to derive an asymptotic expression for the coefficients of a generating function $F(z)$ with help of the dominant singularity and the dominant term of $F(z)$. We state the well-known `transfer theorem' for the specific cases we will need. \begin{thm}[\cite{flajolet1990-transfer}]\label{tt} Let $A(z)$ be a $\Delta$-analytic generating function. \begin{enumerate} \item\label{tt:polynomial} If \begin{equation*} A(z) = P(z) + c\br{1-\rho_A^{-1}z}^{-\alpha} + O\br{\br{1-\rho_A^{-1}z}^{1/4-\alpha}} \end{equation*} with a polynomial $P(z)$ and constants $c\not=0$, $\alpha\in\R\setminus\Z_{\le 0}$, then \[ [z^n]A(z)=\br{1+O\br{n^{-1/4}}}\frac{c}{\Gamma(\alpha)} n^{\alpha-1}\rho_A^{-n}. \] Here, $\Gamma(\alpha):=\int_0^\infty z^{\alpha-1}e^{-z}\dd z$ is the gamma function. \item\label{tt:log} If \begin{equation*} A(z) = P(z) + c\cdot\log\br{1-\rho_A^{-1}z} + O\br{\br{1-\rho_A^{-1}z}^{1/4}}, \end{equation*} then \[ [z^n]A(z)=\br{1+O\br{n^{-1/4}}}(-c) n^{-1}\rho_A^{-n}. \] \end{enumerate} \end{thm} We use the standard notation $\gamma_A=\rho_A^{-1}$ for the exponential growth constant of $[z^n]A(z)$. If we are counting rooted maps or multigraphs, the roots will be counted in the generating function unless stated otherwise. We will often mark vertices or edges of multigraphs or maps, which corresponds to applying the differential operator $z\frac{d}{dz}$ to the generating functions (with $z=x$ if vertices are marked and $z=y$ if edges are marked). To simplify notation we write $\opa{z}$ for $z\frac{d}{dz}$ and $\opa{z}^n$ for repeatedly applying $n$ times the operator $z\frac{d}{dz}$, which corresponds to marking $n$ vertices or edges, while \emph{allowing multiple marks}. We use the notation $F'(z)=\frac{dF}{dz}$ for the standard differential operator.Vice versa, we say that $F$ is a \emph{primitive} of $F'$. The dominant terms of derivatives and primitives of $\Delta$-analytic functions can be determined using Theorems VI.8 and VI.9 from \cite{Flajolet2009-analytic-combinatorics}. Again, we state these results in a slightly different way tailored for our specific needs. \begin{lem}[\cite{Flajolet2009-analytic-combinatorics}]\label{integrating} Let $A(z)$ be a $\Delta$-analytic generating function with the dominant term $A_d(z)$. Suppose that there exists $\beta\in\R$ with \begin{equation*} A(z) = P(z) + A_d(z) + O\br{\br{1-\rho_A^{-1}z}^{-\beta}}, \end{equation*} where $P(z)$ is a polynomial and $\br{1-\rho_A^{-1}z}^{-\beta} = o(A_d(z))$. \begin{enumerate} \item\label{integrating:diff} We have \begin{equation*} A'(z) = P'(z) + A'_d(z) + O\br{\br{1-\rho_A^{-1}z}^{-\beta-1}}. \end{equation*} \item\label{integrating:int} If in addition $A_d(z)=c\br{1-\rho_A^{-1}z}^{-\alpha}$ for some $\alpha\in\R\setminus\Z_{\leq0}$, then for any primitive $\mathbf{A}(z)$ of $A(z)$ there exists a primitive $\mathbf{P}(z)$ of $P(z)$ such that \begin{equation*} \mathbf{A}(z) = \mathbf{P}(z) + \mathbf{A}_d(z) + O(R(z)) \end{equation*} with \begin{equation*} \mathbf{A}_d(z) = \begin{cases} \frac{c\rho_A}{\alpha-1}\br{1-\rho_A^{-1}z}^{-\alpha+1} & \text{if }\alpha\not=1,\\ -c\rho_A\log\br{1-\rho_A^{-1}z} & \text{if }\alpha=1, \end{cases} \end{equation*} and \begin{equation*} R(z) = \begin{cases} \br{1-\rho_A^{-1}z}^{-\beta+1} & \text{if }\beta\not=1,\\ \log\br{1-\rho_A^{-1}z} & \text{if }\beta=1. \end{cases} \end{equation*} \end{enumerate} \end{lem} \Cref{tt} and \Cref{integrating} are very helpful when the generating functions in question are $\Delta$-analytic. However, for many of our generating functions we will not be able to guarantee $\Delta$-analyticity. In order to utilise the results of this section also for generating functions that are \emph{not necessarily} $\Delta$-analytic, we introduce the following concept and notation. \begin{definition}\label{def:cong} Given a generating function $F(z)$ and $\Delta$-analytic functions $A(z)$ and $B(z)$, we say that $F(z)$ is \emph{congruent} to $A(z)+O(B(z))$ and write \begin{equation*} F(z) \cong A(z) + O(B(z)) \end{equation*} if there exist $\Delta$-analytic functions $F^+(z),F^-(z)$ and polynomials $P^+(z),P^-(z)$ such that \begin{itemize} \item $F^- \preceq F \preceq F^+$; \item $F^+(z) = P^+(z) + A(z) + O(B(z))$; \item $F^-(z) = P^-(z) + A(z) + O(B(z))$. \end{itemize} Here we allow $A(z)\equiv 0$. \end{definition} With \Cref{def:cong}, we are able to apply the transfer theorem even if $F$ itself is not $\Delta$-analytic. The following lemma is an immediate consequence of \Cref{tt} and the fact that $F^- \preceq F \preceq F^+$. \begin{lem}\label{congruent:tt} If $F(z) \cong A(z)$, where $A(z)$ is as in~\Cref{tt}, then \begin{equation*} [x^n]F(z) = \br{1+O\br{n^{-1/4}}}[z^n]A(z). \end{equation*} \end{lem} In this paper we will often encounter sums, products, differentials and integrals of generating functions. The following lemma states that these operations are compatible with the notion of congruence. We will frequently use this lemma without explicitly mentioning it. \begin{lem}\label{congruent:meta} Let $A,A_1,A_2,B_1,B_2$ be $\Delta$-analytic functions with only finitely many negative coefficients. Let $F_1,F_2$ be generating functions such that \begin{align*} &F_1(z) \cong A_1(z) + O(B_1(z))& &\text{and}& &F_2(z) \cong A_2(z) + O(B_2(z))& \end{align*} and let $F(z)$ be a generating function with \begin{equation*} F(z) \cong A(z) + O\br{\br{1-\rho_F^{-1}z}^{-\beta}}, \end{equation*} where $\beta\in\R$ and the dominant term $A_d(z)$ of $A(z)$ satisfies $\br{1-\rho_F^{-1}z}^{-\beta}= o(A_d(z))$. Then the following holds. \begin{align*} F_1(z) \pm F_2(z) &\cong A_1(z) \pm A_2(z) + O\Big(B_1(z)) + O(B_2(z)\Big),\\ F_1(z) F_2(z) &\cong A_1(z)A_2(z) + O\Big(A_1(z)B_2(z) + B_1(z)A_2(z) + B_1(z)B_2(z)\Big),\\ F'(z) &\cong A'(z) + O\br{\br{1-\rho_F^{-1}z}^{-\beta-1}}. \end{align*} Furthermore, if $A_d(z)=c\br{1-\rho_F^{-1}z}^{-\alpha}$ for $\alpha\in\R\setminus\Z_{\leq0}$, then for any primitive $\mathbf{F}(z)$ of $F(z)$ we have \begin{equation*} \mathbf{F}(z) \cong \mathbf{A}_d(z) + O\br{R(z)}, \end{equation*} where $\mathbf{A}_d$ and $R$ are as in \Cref{integrating}\ref{integrating:int}. \end{lem} \begin{proof} The first congruence follows immediately from \begin{align*} &F_1^- + F_2^- \preceq F_1 + F_2 \preceq F_1^+ + F_2^+& &\text{and}& &F_1^- - F_2^+ \preceq F_1 - F_2 \preceq F_1^+ - F_2^-.& \end{align*} For the product $F_1(z) \cdot F_2(z)$, we may assume that $F_1^-$ and $F_2^-$ have nonnegative coefficients, since $A_1$ and $A_2$ have only finitely many negative coefficients. Hence \begin{equation*} F_1^- \cdot F_2^- \preceq F_1 \cdot F_2 \preceq F_1^+ \cdot F_2^+ \end{equation*} and the second congruence follows. The last two congruences follow from \Cref{integrating} and the fact that \begin{align*} &(F^-)' \preceq F' \preceq (F^+)'& &\text{and}& &\mathbf{F}^- \preceq \mathbf{F} \preceq \mathbf{F}^+,& \end{align*} where $\mathbf{F}^-,\mathbf{F}^+$ are primitives of $F^-,F^+$, respectively, with $\mathbf{F}^-(0) \le \mathbf{F}(0) \le \mathbf{F}^+(0)$. \end{proof} \subsection{Maps with large facewidth} An \emph{essential circle} on $\Sg$ is a circle that is not contractible to a point on $\Sg$. Let $M$ be an embedding of a multigraph on $\Sg$. An \emph{essential cycle} of $M$ is a cycle of $M$ that is an essential circle on the surface. The \emph{facewidth} $\fw(M)$ of $M$ is the minimal number of intersections of $M$ with an essential circle on $\Sg$. The \emph{edgewidth} $\ew(M)$ of $M$ is defined as the minimal number of edges of an essential cycle of $M$. If $g=0$, there are neither essential circles nor essential cycles and we use the convention $\fw(M)=\ew(M)=\infty$. Observe that if $M$ is connected and \emph{not} a $2$-cell embedding, then $\fw(M)=0$, as an essential circle can be found in any face that is not simply connected. The facewidth $\fw_g(G)$ of a multigraph $G$ that is embeddable on $\Sg$ is defined as the \emph{maximal} facewidth of all its embeddings on $\Sg$. If the genus is clear from the context, we omit it and write $\fw(G)$. When we count multigraphs with restrictions to their facewidth, we indicate the restriction by a superscript to the corresponding generating function, e.g.\ $G^{\fw\ge2}(x)$ for the generating function of all multigraphs with facewidth at least two. Having large facewidth proves to be a very helpful property, because it allows us to derive a constructive decomposition along connectivity as well as the existence of a unique embedding for $3$-connected multigraphs. The following lemma was applied in a similar way in \cite{Chapuy2011-enumeration-graphs-on-surfaces} as later in this paper. \begin{lem}\label{robertsonvitray}\cite{robertson1990-representativity} Let $g>0$ and let $M$ be an embedding of a connected multigraph $G$ on $\Sg$. \begin{enumerate} \item\label{rv1} $M$ has facewidth $\fw(M)=k\geq2$ if and only if $M$ has a unique $2$-connected component embedded on $\Sg$ with facewidth $k$ and all other $2$-connected components of $M$ are planar. \item\label{rv2} If $G$ is $2$-connected, $M$ has facewidth $\fw(M)=k\geq3$ if and only if $M$ has a unique $3$-connected component embedded on $\Sg$ with facewidth $k$ and all other $3$-connected components of $M$ are planar. \item\label{rv3} Let $M_1$, $M_2$ be embeddings of a $3$-connected multigraph on $\Sg$ and suppose that $\fw(M_1)\ge2g+3$. Then there is a homeomorphism of $\Sg$ that maps $M_1$ to $M_2$. \end{enumerate} \end{lem} \Cref{robertsonvitray}(iii) is a generalisation of Whitney's theorem \cite{whitney} that all $3$-connected planar multigraphs have a unique embedding up to orientation on the sphere. Because we will need \Cref{robertsonvitray} for multigraphs rather than for embeddings, we shall use the following easy corollary. \begin{coro}\label{coro:rv} Let $g>0$ and let $G$ be a non-planar connected multigraph strongly embeddable on $\Sg$. \begin{enumerate} \item\label{rvc1} If $\fw_g(G)\ge 2$, then $G$ has a unique $2$-connected non-planar component strongly embeddable on $\Sg$ with facewidth $\fw_g(G)$ and all other $2$-connected components are planar. \item\label{rvc2} If $G$ is $2$-connected and has facewidth $\fw_g(G)\ge 3$, then $G$ has a unique $3$-connected non-planar component strongly embeddable on $\Sg$ with facewidth $\fw_g(G)$ and all other $3$-connected components are planar. \item\label{rvc3} If $G$ is $3$-connected and $\fw_g(G)\ge 2g+3$, then $G$ has a unique $2$-cell embedding on $\Sg$ up to orientation. \end{enumerate} \end{coro} \begin{proof} By \Cref{robertsonvitray}\ref{rv1}, for any fixed embedding of $G$ all but one components are planar. As $G$ itself is not planar, that exceptional component has to be non-planar. As the component structure is the same for \emph{all} embeddings, the non-planar component $I$ is independent of the embedding. Therefore, $I$ is the unique component described in \ref{rvc1}. Part \ref{rvc2} is proved analogously and \ref{rvc3} is a direct consequence of \Cref{robertsonvitray}\ref{rv3}. \end{proof} \section{Maps and triangulations}\label{maps} The goal of this section is to enumerate cubic $3$-connected \emph{maps} on $\Sg$. The duals of these maps are triangulations, which are characterised in the following proposition. \begin{prop} \label{prop:3-conn-dual} Let $M$ be a $2$-cell embedding of a cubic multigraph on $\Sg$ and let $M^*$ be its dual map. Then $M$ is 3-connected if and only if $M^*$ is a triangulation with at least six edges and without separating loops, separating double edges, or separating pairs of loops. \end{prop} \begin{proof} For cubic graphs with at least four vertices (and thus at least six edges), 3-connectivity and 3-edge-connectivity coincide. This can be seen by a simple case analysis. We thus use 3-edge-connectivity hereafter. Since a vertex in $M$ corresponds to a face in $M^*$, deleting edges in the primal $M$ has the same effect as cutting the surface along the dual edges of $M^*$ (for a formal definition of ``cutting'' see Section \ref{sec:def:surgery}), and a set of edges is a separator in $M$ if and only if cutting along the dual edges in $M^*$ separates the surface. Thus, a bridge in $M$ corresponds to a separating loop in $M^*$. A $2$-edge-separator in $M$ corresponds either to a separating double edge or a pair of loops in $M^*$ which together separate the surface. \end{proof} In order to enumerate the triangulations described in \Cref{prop:3-conn-dual}, we will relate them to simple triangulations that have been studied by Bender and Canfield \cite{BENDER1986244}. To this end we will use the following classes of triangulations. Let $\class{M}_g$ be the class of triangulations on $\Sg$ without separating loops, separating double edges, and separating pairs of loops and let $M_g(y)$ be its ordinary generating function. Note that these triangulations are either the duals of $3$-connected cubic maps on $\Sg$ by \Cref{prop:3-conn-dual} or a triangulation with exactly three edges. Furthermore, let $\class{S}_g$ be the class of simple triangulations on $\Sg$ (i.e.\ without loops or double edges) and let $\class{\triangt}_g$ be the class of triangulations on $\Sg$ without separating loops or separating double edges. Let $\triangs_g(y)$ and $\triangt_g(y)$ be their generating functions, respectively. The starting point in obtaining an asymptotic expansion for $M_g(y)$ will be results on simple triangulations which were obtained by Gao \cite{Gao1991-conn-triang} and (in the planar case) by Tutte \cite{tutte1962-planar-triangulations}. However, the results obtained by Gao are not strong enough in order to apply the theory of singularity analysis (developed in \Cref{section:singularity}). We obtain more refined versions of their results by following the ideas of Bender and Canfield \cite{BENDER1986244}. \begin{prop}\label{simplerefined}\label{prop:planar-S} The dominant singularity of $\triangs_g(y)$ is given by $\rho_\triangs=\frac{3}{2^{8/3}}$. The generating function $\triangs_0(y)$ is $\Delta$-analytic and satisfies \begin{align} \triangs_0(y)&=\frac{1}{8}-\frac{9}{16}\br{1-\rho_\triangs^{-1}y}+\frac{3}{2^{5/2}}\br{1-\rho_\triangs^{-1}y}^{3/2} +O\br{\br{1-\rho_\triangs^{-1}y}^{2}}. \end{align} For $g\ge1$ we have \begin{align} \triangs_g(y)&\cong c_g \br{1-\rho_\triangs^{-1} y}^{-5g/2+3/2}\br{1+O\br{\br{1-\rho_\triangs^{-1} y}^{1/4}}}, \end{align} where $c_g$ is a constant depending only on $g$. Furthermore, for $g\ge0$, the asymptotic number of simple triangulations on $\Sg$ with $m$ edges is given by \begin{align*} \abs{\class{\triangs}_g(m)}&=\br{1+O\br{m^{-1/4}}}\frac{c_g}{\Gamma(5(g-1)/2)}m^{5g/2-5/2}\rho_\triangs^{-m}, \end{align*} where $c_0 = \frac{3}{2^{5/2}}$. \end{prop} The exact values of $c_g$ can be found in \cite{Gao1993-pattern}. Along the same lines we obtain similar results for $\triangt_g(y)$. \begin{prop}\label{essentialsimple}\label{prop:planar-T} We have $\triangt_0(y)=\triangs_0(y)$ and for $g\ge1$, \begin{align} \triangt_g(y)&\cong c_g \br{1-\rho_{\triangs}^{-1} y}^{-5g/2+3/2}\br{1+O\br{\br{1-\rho_{\triangs}^{-1} y}^{1/4}}}, \end{align} where $c_g$ is the same constant depending only on $g$ as in \Cref{simplerefined}. Furthermore, for $g\ge0$, the asymptotic number of triangulations without separating loops or separating double edges on $\Sg$ with $m$ edges is given by \begin{align*} \abs{\hat{\class{S}}_g(m)}&=\br{1+O\br{m^{-1/4}}}\frac{c_g}{\Gamma(5g/2-5/2))}m^{5g/2-5/2}\rho_{\triangs}^{-m}. \end{align*} \end{prop} The proofs of \Cref{simplerefined,essentialsimple} can be found in \Cref{proof:gao}. From these two results and the fact that $\class{S}_g\subseteq \class{M}_g\subseteq \class{\triangt}_g$ we obtain immediately our results for the number of triangulations in $\class{M}_g$, i.e.~triangulations on $\Sg$ without separating loops, separating double edges, and separating pairs of loops. \begin{prop}\label{threeconn-dual} The dominant singularity of $M_g(y)$ is given by $\rho_{M}=\rho_\triangs=\frac{3}{2^{8/3}}$. The generating function $M_0(y)$ is $\Delta$-analytic and satisfies \begin{align} M_0(y)&=\frac{1}{8}-\frac{9}{16}\br{1-\rho_M^{-1}y}+\frac{3}{2^{5/2}}\br{1-\rho_M^{-1}y}^{3/2} +O\br{\br{1-\rho_M^{-1}y}^{2}}. \end{align} For $g\ge1$ we have \begin{align} M_g(y)&\cong c_g \br{1-\rho_M^{-1} y}^{-5g/2+3/2}\br{1+O\br{\br{1-\rho_M^{-1} y}^{1/4}}}, \end{align} where $c_g$ is the same constant depending only on $g$ as in \Cref{simplerefined}. Furthermore, for $g\ge0$, the asymptotic number of triangulations in $\class{M}_g(m)$ is given by \begin{align*} \abs{\class{M}_g(m)}&=\br{1+O\br{m^{-1/4}}}\frac{c_g}{\Gamma(5g/2-5/2))}m^{5g/2-5/2}\rho_{M}^{-m}. \end{align*} \end{prop} Observe that from \Cref{threeconn-dual,simplerefined} it follows immediately that the dual of a cubic map on $\Sg$ is simple with high probability, i.e.~with probability tending to one as $m$ tends to infinity. \section{Cubic graphs}\label{graphs} Unless stated otherwise, graphs are unrooted. Recall that, in our generating functions, $x$ marks vertices and $y$ marks edges. Additionally, we will distinguish whether edges are single edges, double edges or loops because they will be treated differently when obtaining relations between graph classes. We will use the variable $z$ to mark double edges and the variable $w$ to mark loops. It is easy to see that $3$-connected cubic graphs are simple and that $2$-connected cubic multigraphs do not contain loops. The generating functions for these classes will only feature the variables of edges that can occur. In order to derive asymptotic results we shall deal with univariate generating functions $F(v)$. As cubic (multi)graphs always have $2n$ vertices and $3n$ edges, where $n\in\N$, the coefficient $(2n)![v^n]F(v)$ will denote the number of graphs (or multigraphs or weighted multigraphs) in the corresponding class with $2n$ vertices and $3n$ edges. Such a univariate generating function can be obtained by the following substitution. \begin{definition}\label{def:univariate} Let $\class{F}$ be a class of connected cubic vertex-labelled multigraphs without triple edges and let \begin{equation*} F(x,y,z,w) = \sum_{n,m,k,l\ge 0}\frac{f_{n,m,k,l}}{n!}x^ny^mz^kw^l \end{equation*} be its exponential generating function. We define functions $F(v)$, $F^u(v)$, and $F^{s}(v)$ as follows. \begin{align*} F(v) &:= F\br{v^{1/4},v^{1/6},\frac{v^{1/3}}{2},\frac{v^{1/6}}{2}}, \\ F^u(v) &:= F(v^{1/4},v^{1/6},v^{1/3},v^{1/6}), \\ F^s(v) &:= F(v^{1/4},v^{1/6},0,0). \end{align*} If the generating function of $\class{F}$ involves only two or three variables, we define $F(v)$, $F^u(v)$, and $F^s(v)$ analogously, only using the substitutions of those variables that occur. \end{definition} We claim that $(2n)![v^n]F(v)$ is the number of weighted multigraphs in $\class{F}(2n)$, i.e.\ the sum of $W(G)$ for all $G\in\class{F}$ with $2n$ vertices (and thus with $3n$ edges). For, if $G\in\class{F}(2n)$ has $k$ double edges, $l$ loops, and $m$ single edges, then there are $2k+l+m = 3n$ edges in total and the substitution transforms the monomial $x^{2n}y^mz^kw^l$ into $2^{-(k+l)}v^{n/2+m/6+k/3+l/6} = W(G)v^n$. Similarly, $(2n)![v^n]F^u(v)$ is the number of (unweighted) multigraphs in $\class{F}(2n)$. Finally, $(2n)![v^n]F^s(v)$ is the number of simple graphs in $\class{F} (2n)$, since replacing $z$ and $w$ by $0$ ensures that no graphs with double edges or loops are counted in $F^s(v)$. \subsection{From maps to graphs} Let $\class{\three}_g$ be the class of $3$-connected cubic vertex-labelled graphs \emph{strongly embeddable} on $\Sg$ and let $\three_g(x,y)$ be its generating function. In this section we provide some necessary properties of $\three_g(v)$. We will use the auxiliary classes $\ol{\class{\three}}_g$ of $3$-connected cubic \emph{edge-labelled} graphs strongly embeddable on $\Sg$, and $\ol{\class{\triangm}}_g$ of \emph{edge-labelled, unrooted} triangulations where the triangulations are in $\class{\triangm}_g$. \begin{prop}\label{coro:3-conn-graphs} The dominant singularity of $\vertex{\three}_g(v)$ is $\rho_{\three}=\rho_{\triangs}^3=\frac{27}{256}$ and we have the following congruences. \begin{align*} \vertex{\three}_0(v)&\cong c_0\left( 1 - \rho_\three^{-1} v\right)^{5/2}+O\br{\br{1 - \rho_\three^{-1} v}^3}, & &\\ \vertex{\three}_1(v)&\cong c_1\log\left( 1 - \rho_\three^{-1}v\right)+O\br{\br{1 - \rho_\three^{-1} v}^{1/4}}, &&\\ \vertex{\three}_g(v)&\cong c_g\left( 1 - \rho_\three^{-1} v \right)^{-5g/2+5/2}+O\br{\br{1 - \rho_\three^{-1} v}^{-5g/2+11/4}} &\text{for }g\ge 2,& \end{align*} where $c_g$ is the same constant depending only on $g$ as in \Cref{simplerefined}. \end{prop} Applying \Cref{tt}, we immediately obtain the coefficients of $\three_g(v)$. \begin{coro} The coefficients of $\vertex{\three}_g(v)$ satisfy \[ [v^n]\vertex{\three}_g(v) =\br{1+O\br{n^{-1/4}}} \ol{c}_g n^{5(g-1)/2-1} \rho_{\three}^{-n}, \] where $\ol{c}_g$ is a constant depending only on $g$. \end{coro} \begin{proof}[Proof of \Cref{coro:3-conn-graphs}] First we compare $\class{\triangm}_g$ and $\ol{\class{\triangm}}_g$. For each triangulation $M\in\class{\triangm}_g$ with $m$ edges, there are $m!$ possibilities of labelling its edges. Conversely, for a triangulation $\ol{M}\in\ol{\class{\triangm}}_g$, there are $2m$ possibilities of rooting. Therefore, the exponential generating function $\ol{\triangm}_g(y)$ of $\ol{\class{\triangm}}_g$ satisfies \[ [y^m]\triangm_g(y) = 2m [y^m]\ol{\triangm}_g(y)\] and thus \[\triangm_g(y)=2\opa{y}\ol{\triangm}_g(y).\] Every graph $G\in \ol{\class{\three}}_g$ has at least two (edge-labelled) $2$-cell embeddings. By \Cref{prop:3-conn-dual}, the maps obtained in this way are precisely the duals of triangulations in $\ol{\class{\triangm}}_g$. As $y$ marks the number of edges in $\ol{\triangm}_g(v^{1/3})$ and $v$ marks a third of the number of edges in $\ol{\three}_g(v)$, we obtain \begin{equation*} 2\ol{\three}_g(v) \preceq \ol{\triangm}_g(v^{1/3}). \end{equation*} We claim that, for a cubic map $M$ on $\Sg$, its facewidth $\fw(M)$ is exactly the edgewidth $\ew(M^*)$ of the triangulation $M^*$ that is the dual of $M$. To see this, we observe that an essential cycle of $M^*$ witnessing the edgewidth of $M^*$ corresponds to an essential circle on $\Sg$ that meets $M$ in $\ew(M^*)$ edges and no vertices, resulting in $\fw(M)\leq\ew(M^*)$. On the other hand, any two faces of $M$ that share a vertex also share an edge, as $M$ is cubic. Thus, there is an essential circle witnessing the facewidth of $M$ that meets $M$ only at edges. As this circle corresponds to an essential cycle of $M^*$, we have $\fw(M)\geq\ew(M^*)$. Since by \Cref{robertsonvitray}(iii) a $3$-connected graph embeddable on $\Sg$ with facewidth at least $2g+3$ has exactly two embeddings, we have \begin{equation*} 2\ol{\three}^{\fw \geq 2g+3}_g(v) = \ol{\triangm}^{\ew \geq 2g+3}_g(v^{1/3}). \end{equation*} As obviously $\ol{\three}_g^{\fw \geq 2g+3}(v) \preceq \ol{\three}_g(v)$, we obtain the following relations: \begin{equation}\label{eq:G-to-M} \ol{\triangm}^{\ew \geq 2g+3}_g(v^{1/3})=2\ol{\three}^{\fw \geq 2g+3}_g(v)\preceq 2\ol{\three}_g(v) \preceq \ol{\triangm}_g(v^{1/3}). \end{equation} Since there are no double edges in a $3$-connected cubic graph, we know that the two generating functions $\ol\three_g(v)$ and $\three_g(v)$ are closely related. To be precise, $(2n)![v^n]\three_g(v)$ is the number of vertex-labelled graphs in $\class{\three}_g(2n)$. Since every such graph has $3n$ edges, $(3n)!(2n)![v^n]\three_g(v)$ is the number of $3$-connected cubic graphs with $2n$ vertices embeddable on $\Sg$ with both vertices and edges labelled. As this number is equal to $(2n)!(3n)![v^n]\ol{\three}_g(v)$ by an analogous argument, we have \begin{equation*} [v^n]\three_g(v)=[v^n]\ol{\three}_g(v). \end{equation*} Therefore, we can replace $\ol{\three}_g(v)$ by $\three_g(v)$ in \eqref{eq:G-to-M} to obtain \begin{align*} \three_g(v)\preceq\frac{1}{2}\ol{\triangm}_g(v^{1/3})=\left.\frac{1}{4}\int t^{-1}\triangm_g(t)\dd t \right|_{t=v^{1/3}}. \end{align*} By \Cref{integrating} we obtain an upper bound for $\three_g(v)$ as claimed. To finish the proof we will show the following claim. \setcounter{claim}{0} \begin{claim}\label{claim:largeew} The generating functions $\triangm_g(y)^{\ew \geq 2g+3}$ and $\triangm_g(y)$ have the same dominant singularity and \[\triangm_g(y)-\triangm_g^{\ew \geq 2g+3}(y)\cong O\br{\br{1-\rho_S^{-1}y}^{-5g/2+7/4}}.\] \end{claim} Before we prove the claim, let us note that \Cref{coro:3-conn-graphs} follows immediately from \Cref{claim:largeew}, \Cref{congruent:meta}, and \Cref{threeconn-dual}. A statement more general than \Cref{claim:largeew} was proven in \cite{representativity} for a variety of map classes. Although we believe that the proof in \cite{representativity} generalises to $\class{\triangm}_g$, which was not considered in \cite{representativity}, we give a slightly different proof here for completeness. The generating function of $\class{\triangm}_g \setminus \class{\triangs}_g$ is congruent to $O\br{\br{1-\rho_S^{-1}y}^{-5g/2+7/4}}$ by \Cref{essentialsimple,simplerefined,threeconn-dual}. It thus suffices to show that \[\triangs_g^{\ew\le2g+2} \cong O\br{\br{1-\rho_S^{-1}y}^{-5g/2+7/4}}.\] For $i\ge 3$, let $\class\triangs^{C=i}_g$ be the class of triangulations in $\class\triangs_g$ where one non-contractible cycle $C$ of length $i$ is marked, and we denote its generating function by $\triangs^{C=i}_g(y)$. Clearly $\triangs^{\ew=i}_g(y) \preceq \triangs^{C=i}_g(y)$. Let $M\in\class\triangs_g^{C=i}$ and let $C$ be the marked cycle of $M$. Consider the surface $\Sg$ on which $M$ embeds. We cut $\Sg$ along the cycle $C$, and duplicate the vertices and edges of $C$ so that the map structure in the neighbourhood on the two sides of $C$ is preserved (for a precise definition of ``cut'', see Section~\ref{sec:def:surgery} in the appendix). We then close the two resulting holes by inserting disks to them in $\Sg$. This operation is also called ``cutting along $C$ on $\Sg$'', and a more general and rigorous definition of such topological surgeries can be found in \Cref{proof:gao}. For each of the two disks, we then add a new vertex inside the disk and use it to triangulate the disk (see \Cref{fig:wheel}). If $C$ was separating, we mark one of the corners at the inserted vertex in the component that contains the original root face of $M$. For the other component, we choose one of the corners at the inserted vertex to be its root. If $C$ was not separating, then we mark one corner at each of the two inserted vertices. In total we add $3i$ edges to the map. These operations result in \begin{itemize} \item two triangulations $M^{(1)}, M^{(2)}$, where $M^{(1)}$ contains the original root face of $M$ and a marked corner; \item or one triangulation $M^*$ with two marked corners. \end{itemize} All resulting triangulations are in $\class\triangs_{g'}$ for some $g'=triangle 45,x=0.9cm,y=1.0cm] \clip(-0.1,-2.6) rectangle (13.1,0.1); \draw [shift={(2.5,-11.5)},color=black] plot[domain=1.3:1.85,variable=\t]({9.34*cos(\t r)},{9.34*sin(\t r)}); \draw [shift={(2.5,9.)},color=black] plot[domain=4.44:4.98,variable=\t]({9.34*cos(\t r)},{9.34*sin(\t r)}); \draw [shift={(10.5,-11.5)},color=black] plot[domain=1.3:1.42,variable=\t]({9.34*cos(\t r)},{9.34*sin(\t r)}); \draw [shift={(10.5,-11.5)},color=black] plot[domain=1.72:1.84,variable=\t]({9.34*cos(\t r)},{9.34*sin(\t r)}); \draw [shift={(10.5,9.)},color=black] plot[domain=4.44:4.56,variable=\t]({9.34*cos(\t r)},{9.34*sin(\t r)}); \draw [shift={(10.5,9.)},color=black] plot[domain=4.86:4.98,variable=\t]({9.34*cos(\t r)},{9.34*sin(\t r)}); \draw [rotate around={-90.:(2.5,-1.25)},color=red] (2.5,-1.25) ellipse (0.9cm and 0.24cm); \draw [color=red](2.78,-1.17) node[anchor=north west] {C}; \draw [rotate around={-90:(9.14,-1.25)},color=red] (9.14,-1.25) ellipse (1.cm and 0.6cm); \draw [rotate around={-90:(11.86,-1.25)},color=red] (11.86,-1.25) ellipse (1.cm and 0.6cm); \draw [color=red] (9.14,-0.24)-- (9.15,-1.12); \draw [color=red] (9.15,-1.12)-- (9.67,-0.77); \draw [color=red] (9.15,-1.12)-- (9.71,-1.58); \draw [color=red] (9.15,-1.12)-- (9.15,-2.26); \draw [color=red] (9.15,-1.12)-- (8.56,-1.49); \draw [color=red] (9.15,-1.12)-- (8.63,-0.72); \draw [color=red] (11.86,-1.2)-- (11.86,-0.24); \draw [color=red] (11.86,-1.2)-- (12.37,-0.74); \draw [color=red] (11.86,-1.2)-- (12.37,-1.78); \draw [color=red] (11.86,-1.2)-- (11.86,-2.26); \draw [color=red] (11.86,-1.2)-- (11.34,-1.79); \draw [color=red] (11.86,-1.2)-- (11.28,-0.92); \begin{scriptsize} \draw [fill=red] (2.50,-0.34) circle (1.5pt); \draw [fill=red] (2.5,-2.16) circle (1.5pt); \draw [fill=red] (2.30,-0.75) circle (1.5pt); \draw [fill=red] (2.30,-1.75) circle (1.5pt); \draw [fill=red] (2.70,-0.75) circle (1.5pt); \draw [fill=red] (2.72,-1.61) circle (1.5pt); \draw [fill=red] (9.15,-2.26) circle (1.5pt); \draw [fill=red] (9.14,-0.24) circle (1.5pt); \draw [fill=red] (8.63,-0.72) circle (1.5pt); \draw [fill=red] (8.56,-1.49) circle (1.5pt); \draw [fill=red] (9.67,-0.77) circle (1.5pt); \draw [fill=red] (9.71,-1.58) circle (1.5pt); \draw [fill=red] (9.15,-1.12) circle (1.5pt); \draw [fill=red] (11.86,-2.26) circle (1.5pt); \draw [fill=red] (11.86,-0.24) circle (1.5pt); \draw [fill=red] (11.35,-1.79) circle (1.5pt); \draw [fill=red] (11.29,-0.92) circle (1.5pt); \draw [fill=red] (12.37,-0.74) circle (1.5pt); \draw [fill=red] (12.37,-1.78) circle (1.5pt); \draw [fill=red] (11.86,-1.23) circle (1.5pt); \end{scriptsize} \end{tikzpicture} \caption{Cutting along $C$ and triangulating the inserted disc.}\label{fig:wheel} \end{figure} Since a corner $(v_0,e,e')$ is uniquely defined once $v_0$ and $e$ are given, marking a corner is equivalent to marking an edge and choosing one of its end vertices. In terms of generating functions, this corresponds to applying the operator $2\opa{y}=2y\deriv{y}$. As in previous proofs, we will mark repeatedly, which will result in overcounting. Since we added $3i$ edges to $M$ by our construction, we have to compensate by a factor of $y^{3i}$. Therefore, we obtain the relation \[ y^{3i}\triangs^{C=i}_g(y) \preceq 4\opa{y}^2\br{\triangs_{g-1}(y)} + \sum_{\substack{g_1 + g_2 = g \\ g_1,g_2 \geq 1}} 2\opa{y}\br{\triangs_{g_1}(y)} \triangs_{g_2}(y).\] By \Cref{simplerefined}, we know that \[4\opa{y}^2\br{\triangs_{g-1}(y)} + \sum_{\substack{g_1 + g_2 = g \\ g_j \geq 1}} 2\opa{y}\br{\triangs_{g_1}(y)} \triangs_{g_2}(y)\cong O\br{\br{1-\rho_S^{-1}y}^{-5g/2+7/4}}. \] Because \[ \triangs_g^{\ew\le2g+2}(y) = \sum_{i=3}^{2g+2}\triangs_g^{\ew=i}(y) \preceq \sum_{i=3}^{2g+2}\triangs^{C=i}_g(y), \] we complete the proof of the claim. \end{proof} \subsection{From 3-connected graphs to connected multigraphs} In this section we derive dominance relations between different classes of cubic multigraphs. In the end we will relate connected cubic multigraphs via $2$-connected cubic multigraphs to $3$-connected cubic graphs enumerated in the previous section. Denote by $\class{\three}_g$, $\class{\two}_g$, and $\class{\one}_g$ the classes of $3$-connected, $2$-connected, and connected vertex-labelled cubic multigraphs strongly embeddable on $\Sg$, respectively. Additionally, let $\three_g(x,y)=\sum \frac{d_{n,m}}{n!}x^ny^m$, $\two_g(x,y,z)=\sum \frac{b_{n,m,k}}{n!}x^ny^mz^k$, and $\one_g(x,y,z,w)=\sum \frac{c_{n,m,k,l}}{n!}x^ny^mz^kw^l$, be the corresponding generating functions. In the generating function $\one_g(x,y,z,w)$, the graph $\Phi$ consisting of two vertices connected by three edges will not be taken into account. This graph will be treated separately at the end. First we give a relation between a subclass of $\class{\three}_g$ and a subclass of $\class{\two}_g$. To do this we need the class $\class{\network}$ of edge-rooted 2-connected vertex-labelled cubic planar multigraphs, called \emph{networks}. In the exponential generating function $N(x,y,z)$ of $\class{N}$ we mark the root always with $y$ as a single edge, and with $z$ marking double edges not including the root edge. \begin{lem}\label{2conngf} For $g\ge 1$, the generating functions of $\class\three_g$ and $\class\two_g$ satisfy \begin{align}\label{eq:threetwo} \vertex{\three}_g^{\fw\ge3}(x,\oy)&-\vertex{\three}_0(x,\oy)\preceq \vertex{\two}_g^{\fw\ge3}(x,y,z)\preceq \vertex{\three}_g^{\fw\ge3}(x,\oy), \end{align} where $\oy=y(1+N(x,y,z))$. \end{lem} \begin{proof} Let $B$ be a multigraph in $\class{\two}_g^{\fw\ge3}$. We show that it is counted at least once on the right-hand side and at most once on the left-hand side of \eqref{eq:threetwo}. First, suppose that $B$ is not planar. Then \Cref{coro:rv}\ref{rvc2} states that $B$ has a unique $3$-connected component $T$ strongly embeddable on $\Sg$ with the same facewidth. $T$ is in $\class{\three}_g^{\fw\ge3}$ and therefore counted once in $\three_g^{\fw\ge3}(x,y)$. To get $B$ from $T$, we have to attach $2$-connected components along the edges (see \Cref{fig:3to2}). That means, either we leave an edge as it is (obtaining a summand of $y$) or we replace it by two edges (obtaining a factor of $y^2$) and one multigraph in $\class{\network}$ without its root edge (obtaining a factor of $\frac{1}{y}N$). Thus, $B$ is counted exactly once on the right-hand side of \eqref{eq:threetwo}. \begin{figure}[htbp] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm,scale=1] \draw(-6.,0.)--(-4.,2.); \draw(-4.,2.)--(-4.,4.); \draw(-2.,0.)--(-4.,4.); \draw(-6.,0.)--(-4.,4.); \draw(-6.,0.)--(-2.,0.); \draw(-4.,2.)--(-2.,0.); \draw[fill=black](-6.,0.)circle (1.5pt); \draw[fill=black](-2.,0.)circle (1.5pt); \draw[fill=black](-4.,2.)circle (1.5pt); \draw[fill=black](-4.,4.)circle (1.5pt); \draw[->](-2,2) -- (0,2); \draw [fill=gray] (2.06,0.) ellipse (0.84cm and 0.4cm); \draw [rotate around={63.435:(1.044,2.088)},fill=gray] (1.044,2.088) ellipse (0.73cm and 0.37cm); \draw [rotate around={-45.0628:(2.7245,1.2735)},fill=gray] (2.7245,1.2735) ellipse (0.64cm and 0.34cm); \draw (2.06,0) node{$N$}; \draw (1.044,2.088) node{$N$}; \draw (2.7245,1.2735) node{$N$}; \draw(0.,0.)--(0.718,1.436); \draw(1.370,2.740)--(2.,4.); \draw(0.,0.)--(1.22,0.); \draw(2.9,0.)--(4.,0.); \draw(2.269,1.730)--(2.,2.); \draw(3.182,0.817)--(4.,0.); \draw(0.,0.)--(2.,2.); \draw(2.,2.)--(2.,4.); \draw(4.,0.)--(2.,4.); \draw[fill=black](0.,0.)circle (1.5pt); \draw[fill=black](4.,0.)circle (1.5pt); \draw[fill=black](2.,2.)circle (1.5pt); \draw[fill=black](2.,4.)circle (1.5pt); \draw[fill=black](1.22,0.)circle (1.5pt); \draw[fill=black](3.182,0.817)circle (1.5pt); \draw[fill=black](1.370,2.740)circle (1.5pt); \draw[fill=black](0.718,1.436)circle (1.5pt); \draw[fill=black](2.9,0.)circle (1.5pt); \draw[fill=black](2.269,1.730)circle (1.5pt); \end{tikzpicture} \caption{Obtaining $2$-connected graphs from $3$-connected graphs by substituting edges with networks.}\label{fig:3to2} \end{figure} If $B$ is planar, then it might be counted more than once on the right-hand side. Indeed, in this case the $2$-connected components carrying the facewidth might be different for different embeddings. Therefore, $\vertex{\three_g}^{\fw\ge3}(x,y+y\vertex{\network}(x,y,z))$ is an upper bound. To get a lower bound we have to subtract all multigraphs we overcounted. This is achieved by subtracting $\three_0(x,y+y\network(x,y,z))$, as only planar multigraphs are overcounted and each such multigraph is subtracted once for each of its $3$-connected components. \end{proof} In the same spirit we can relate connected and $2$-connected multigraphs, using the auxiliary class $\class{Q}$ of all edge-rooted connected vertex-labelled cubic planar multigraphs whose root edge is a loop. To simplify the formulas later on, the root will be marked by $y$ in the generating function $Q(x,y,z,w)$ and only non-root loops are marked by $w$. \begin{lem}\label{conngf} For $g\ge1$ the generating functions of $\class\one_g$ and $\class\two_g$ satisfy the following relation: \begin{align}\label{eq:conngf} \two_g^{\fw\ge2}(x,\oy,\oz)-\two_0(x,\oy,\oz)&\preceq\one_g^{\fw\ge2}(x,y,z,w)\preceq \two_g^{\fw\ge2}(x,\oy,\oz), \end{align} where $\oy=\frac{y}{1-Q(x,y,z,w)}$ and $\oz=\frac{1}{2}(\frac{y}{1-Q(x,y,z,w)})^2 - \frac{y^2}{2} + z$. \end{lem} \begin{proof} Let $C\in\class{\one}_g^{\fw\ge2}$. We shall show that $C$ is counted at least once on the right-hand side and at most once on the left-hand side of \eqref{eq:conngf}. First, suppose that $C$ is not planar. Then \Cref{coro:rv}\ref{rvc1} states that $C$ has a unique $2$-connected component $B$ strongly embeddable on $\Sg$ with the same facewidth, i.e., $B\in\class{\two}_g^{\fw\ge2}$. To construct $C$ from $B$ we have to replace each edge by a sequence of edges and multigraphs in $\class{Q}$, which means we replace one edge by a sequence of alternating edges and multigraphs in $\class{Q}$ without the root, starting and ending with an edge. Therefore, the replacement leads to the substitution $y\mapsto y\frac{1}{1-Q(x,y,z,w)}$ (see \Cref{fig:2to1}). \begin{figure}[htbp] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm,scale=1] \draw(-5.,0.)--(-2.,0.); \draw(-2.,0.)--(-2.5,2.); \draw(-2.,0.)--(-1.5,2.); \draw(-2.,4.)--(-5.,4.); \draw(-2.5,2.)--(-1.5,2.); \draw(-2.5,2.)--(-2.,4.); \draw(-1.5,2.)--(-2.,4.); \draw(-5,0) to[out=70,in=290] (-5,4); \draw(-5,0) to[out=110,in=250] (-5,4); \draw[fill=black](-5.,0.)circle (1.5pt); \draw[fill=black](-2.,0.)circle (1.5pt); \draw[fill=black](-5.,4.)circle (1.5pt); \draw[fill=black](-2.,4.)circle (1.5pt); \draw[fill=black](-2.5,2)circle (1.5pt); \draw[fill=black](-1.5,2)circle (1.5pt); \draw[->](-1,2) -- (0,2); \draw[fill=gray](1.5,-1.1)circle(.5cm); \draw[fill=gray](2.5,1.5)circle(.5cm); \draw[fill=gray](3.5,-1.1)circle(.5cm); \draw[fill=gray](2.5,2.9)circle(.5cm); \draw(1.,0.)--(4.,0.); \draw(4.,0.)--(3.5,2.); \draw(4.,0.)--(4.5,2.); \draw(4.,4.)--(1.,4.); \draw(3.5,2.)--(4.5,2.); \draw(3.5,2.)--(4.,4.); \draw(4.5,2.)--(4.,4.); \draw(1,0) to[out=70,in=290] (1,4); \draw(1,0) to[out=110,in=250] (1,4); \draw(1.5,0.)--(1.5,-0.6); \draw(2.05,1.7)--(1.4,2); \draw(3.5,0.)--(3.5,-0.6); \draw(2.5,4.)--(2.5,3.4); \draw[fill=black](1.,0.)circle (1.5pt); \draw[fill=black](4.,0.)circle (1.5pt); \draw[fill=black](1.,4.)circle (1.5pt); \draw[fill=black](4.,4.)circle (1.5pt); \draw[fill=black](3.5,2)circle (1.5pt); \draw[fill=black](4.5,2)circle (1.5pt); \draw[fill=black](1.5,0.)circle (1.5pt); \draw[fill=black](1.4,2)circle (1.5pt); \draw[fill=black](3.5,0.)circle (1.5pt); \draw[fill=black](2.5,4.)circle (1.5pt); \draw[fill=black](1.5,-0.6)circle (1.5pt); \draw[fill=black](3.5,-0.6)circle (1.5pt); \draw[fill=black](2.05,1.7)circle (1.5pt); \draw[fill=black](2.5,3.4)circle (1.5pt); \draw (1.5,-1.1) node{$Q$}; \draw (2.5,1.5) node{$Q$}; \draw (2.5,2.9) node{$Q$}; \draw (3.5,-1.1) node{$Q$}; \end{tikzpicture} \caption{Obtaining connected graphs from $2$-connected graphs by substituting edges with sequences of $Q$-graphs.}\label{fig:2to1} \end{figure} This results in a $1$-to-$1$ correspondence between the generating functions $\vertex{\two_g}^{\fw\ge2} (x,\oy,\oz)$ and $\vertex{\one_g}^{\fw\ge2}(x,y,z,w)$ for non-planar multigraphs. The replacement for double edges results from replacing a set of two edges each as above, except when the two edges are left intact, then they should still be treated as a double edge instead of two simple edges. We thus have the correction term $-\frac{y^2}{2} + z$. As in \Cref{2conngf}, if $C$ is planar, the above argument does not necessarily result in a bijection. We thus have to subtract all corresponding planar multigraphs again in order to avoid overcounting on the left-hand side. Therefore, we get the claimed result analogously to \Cref{2conngf}. \end{proof} Combining \Cref{2conngf,conngf}, we have the following upper and lower bounds for the generating function $C_g(x,y,z,w)$. \begin{coro}\label{conngf-bounds} For $g \geq 1$, the generating function $C_g(x,y,z,w)$ satisfies \begin{align} \begin{split} \label{eq:conngf-bounds} &\quad \quad \; \; \vertex{\three_g}^{\fw \geq 3}\left(x, \oy\left(1+\network(x, \oy, \oz)\right)\right) - \vertex{\three_0} \left(x, \oy\left(1+\network(x, \oy, \oz)\right)\right) \\ &\quad \; + \vertex{\two_g}^{\fw=2}(x, \oy, \oz) - \vertex{\two_0}(x, \oy, \oz) + \vertex{\one_g}^{\fw=1}(x, y, z, w) \\ &\preceq \vertex{\one_g}(x, y, z, w) \\ &\preceq \vertex{\three_g}^{\fw \geq 3}\left(x, \oy\left(1+\network(x, \oy, \oz)\right)\right) + \vertex{\two_g}^{\fw=2}(x, \oy, \oz) + \vertex{\one_g}^{\fw=1}(x, y, z, w), \\ \end{split} \end{align} where $\oy = \frac{y}{1-Q(x,y,z,w)}$ and $\oz = \frac{1}{2} \left( \frac{y}{1-Q(x,y,z,w)} \right)^2 - \frac{y^2}{2} + z$ as in \Cref{conngf}. \end{coro} We note that the upper and lower bounds of $\vertex{\one_g}(x, y, z, w)$ differ only by terms involving generating functions of planar graphs. In \Cref{sec:asy} we will show that those generating functions are subdominant. Therefore, the two bounds match in asymptotics. We will also provide the asymptotic expressions for the other terms in \Cref{sec:asy}. In order to do that, we first establish bounds on the generating functions for multigraph classes with fixed facewidth. \begin{lem}\label{lem:small-fw} For $g\ge 1$ the following relations hold. \begin{align} \vertex{\two_g}^{\fw=2}(x,&y,z) \preceq 2 \br{y+\frac{z}{y}}^2\br{\frac1y+\frac yz}^2 \bigg(\opb{y}{z}^2\br{\vertex{\two_{g-1}^{\fw\ge2}}(x,y,z)}\nonumber\\ &+\sum_{g'=1}^{g-1}\opb{y}{z}\br{\two_{g'}^{\fw\ge2}(x,y,z)}\opb{y}{z}\br{\two_{g-g'}^{\fw\ge2} (x,y,z)}\bigg),\label{eq:2-conn-graphs-fw2}\\ \vertex{\one_g}^{\fw=1}(x,&y,z,w)\preceq \br{xyw}^2\br{\frac1y+\frac yz}\bigg(\opa{w}^2\br{\vertex{\one_{g-1}} (x,y,z,w)}\nonumber\\ &+\sum_{g'=1}^{g-1}\opa{w}\br{\vertex{\one_{g'}}(x,y,z,w)}\opa{w}\br{\vertex{\one_{g-g'}}(x,y,z,w)}\bigg). \label{eq:conn-graphs-fw1} \end{align} \end{lem} \begin{proof} In order to show \eqref{eq:2-conn-graphs-fw2}, let $B$ be a multigraph in $\class{\two}_g^{\fw=2}$. Consider a fixed $2$-cell embedding $M$ of $B$ on $\Sg$ with facewidth two and let $\{e_1=\{v_1,w_1\},e_2=\{v_2,w_2\}\}$ be two edges such that there exists an essential circle $C$ on $\Sg$ meeting $M$ only in $e_1$ and $e_2$. Note that $e_1$, $e_2$ do not share vertices, because otherwise the facewidth would have been one. Then we delete $e_1$ and $e_2$, cut the surface along $C$ and close both holes with a disk\footnote{For a formal definition of this operation see Section~\ref{sec:def:surgery}} (see \Cref{fig:cut}). By this surgery we either disconnect the surface or we reduce its genus by one. \begin{figure}[htbp] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm,scale=0.85] \clip(-0.1,-3.) rectangle (13.5,0.5); \draw [shift={(2.5,-11.5)},color=black] plot[domain=1.3:1.9,variable=\t]({9.487*cos(\t r)+0.*9.487*sin(\t r)},{0.*9.487*cos(\t r)+9.487*sin(\t r)}); \draw [shift={(2.5,9.)},color=black] plot[domain=4.35:4.98,variable=\t]({9.487*cos(\t r)+0.*9.487*sin(\t r)},{0.*9.487*cos(\t r)+9.487*sin(\t r)}); \draw [color=black] (0.,-0.5)-- (1.,-0.75); \draw [color=black] (0.,-1.)-- (1.,-0.75); \draw [color=black] (1.,-0.75)-- (4.,-0.75); \draw [color=black] (4.,-0.75)-- (5.,-0.5); \draw [color=black] (4.,-0.75)-- (5.,-1.); \draw [color=black] (0.,-1.5)-- (1.,-1.75); \draw [color=black] (1.,-1.75)-- (0.,-2.); \draw [color=black] (1.,-1.75)-- (4.,-1.75); \draw [color=black] (4.,-1.75)-- (5.,-1.5); \draw [color=black] (4.,-1.75)-- (5.,-2.); \draw [color=black] (12.,-0.75)-- (13.,-0.5); \draw [color=black] (12.,-0.75)-- (13.,-1.); \draw [color=black] (12.,-1.75)-- (13.,-1.5); \draw [color=black] (12.,-1.75)-- (13.,-2.); \draw [color=black] (8.,-0.5)-- (9.,-0.75); \draw [color=black] (9.,-0.75)-- (8.,-1.); \draw [color=black] (8.,-1.5)-- (9.,-1.75); \draw [color=black] (9.,-1.75)-- (8.,-2.); \draw [shift={(8.825,-1.25)},color=black] plot[domain=-1.395:1.3928,variable=\t]({0.99*cos(\t r)+0.*0.99*sin(\t r)},{0.*0.99*cos(\t r)+0.99*sin(\t r)}); \draw [shift={(12.17,-1.25)},color=black] plot[domain=1.738:4.540,variable=\t]({0.99*cos(\t r)+0.*0.99*sin(\t r)},{0.*0.99*cos(\t r)+0.99*sin(\t r)}); \draw [shift={(10,-11.5)},color=black] plot[domain=1.249:1.358,variable=\t]({9.487*cos(\t r)+0.*9.487*sin(\t r)},{0.*9.487*cos(\t r)+9.487*sin(\t r)}); \draw [shift={(11,-11.5)},color=black] plot[domain=1.783:1.892,variable=\t]({9.487*cos(\t r)+0.*9.487*sin(\t r)},{0.*9.487*cos(\t r)+9.487*sin(\t r)}); \draw [shift={(11,9.)},color=black] plot[domain=4.390:4.5,variable=\t]({9.487*cos(\t r)+0.*9.487*sin(\t r)},{0.*9.487*cos(\t r)+9.487*sin(\t r)}); \draw [shift={(10,9.)},color=black] plot[domain=4.925:5.034,variable=\t]({9.487*cos(\t r)+0.*9.487*sin(\t r)},{0.*9.487*cos(\t r)+9.487*sin(\t r)}); \draw [dash pattern=on 1pt off 1pt,color=black] (9.,-1.75)-- (9.,-0.75); \draw [dash pattern=on 1pt off 1pt,color=black] (12.,-0.75)-- (12.,-1.75); \draw [color=red] (2.5,-0.5) arc (90:270:0.263cm and 0.763cm); \draw [color=red,dash pattern=on2pt off 2pt] (2.5,-2.) arc (270:450:0.263cm and 0.763cm); \draw [color=red](3,-1.3) node {C}; \draw[->](5.5,-1.25) -- (7.5,-1.25); \begin{scriptsize} \draw [fill=black] (1.,-0.75) circle (1.5pt); \draw[color=black] (1.,-1) node {$v_1$}; \draw [fill=black] (1.,-1.75) circle (1.5pt); \draw[color=black] (1.,-1.48) node {$v_2$}; \draw [fill=black] (4.,-0.75) circle (1.5pt); \draw[color=black] (3.8,-1) node {$w_1$}; \draw [fill=black] (4.,-1.75) circle (1.5pt); \draw[color=black] (3.8,-1.48) node {$w_2$}; \draw [fill=black] (0.,-0.5) circle (1.5pt); \draw [fill=black] (0.,-1.) circle (1.5pt); \draw [fill=black] (0.,-1.5) circle (1.5pt); \draw [fill=black] (0.,-2.) circle (1.5pt); \draw [fill=black] (5.,-0.5) circle (1.5pt); \draw [fill=black] (5.,-1.) circle (1.5pt); \draw [fill=black] (5.,-1.5) circle (1.5pt); \draw [fill=black] (5.,-2.) circle (1.5pt); \draw[color=black] (1.67,-1) node {$e_1$}; \draw[color=black] (1.67,-1.58) node {$e_2$}; \draw [fill=black] (9.,-0.75) circle (1.5pt); \draw[color=black] (9.3,-0.72) node {$v_1$}; \draw [fill=black] (9.,-1.75) circle (1.5pt); \draw[color=black] (9.3,-1.72) node {$v_2$}; \draw [fill=black] (12.,-0.75) circle (1.5pt); \draw[color=black] (11.75,-0.72) node {$w_1$}; \draw [fill=black] (12.,-1.75) circle (1.5pt); \draw[color=black] (11.75,-1.72) node {$w_2$}; \draw [fill=black] (13.,-0.5) circle (1.5pt); \draw [fill=black] (13.,-1.) circle (1.5pt); \draw [fill=black] (13.,-1.5) circle (1.5pt); \draw [fill=black] (13.,-2.) circle (1.5pt); \draw [fill=black] (8.,-0.5) circle (1.5pt); \draw [fill=black] (8.,-1.) circle (1.5pt); \draw [fill=black] (8.,-1.5) circle (1.5pt); \draw [fill=black] (8.,-2.) circle (1.5pt); \draw[color=black] (9.25,-1.25) node {$e_3$}; \draw[color=black] (11.8,-1.25) node {$e_4$}; \end{scriptsize} \end{tikzpicture} \caption{Surgery along an essential circle.}\label{fig:cut} \end{figure} \emph{Case 1:} Cutting along $C$ disconnects the surface. As $C$ was an essential loop, both components have genus at least one. Therefore, we obtain two multigraphs $B_1^*$ and $B_2^*$, strongly embeddable on $\torus{g_1}$ and $\torus{g_2}$ respectively, with $g_1,g_2\ge1$ and $g_1+g_2=g$. Without loss of generality, we can assume that $v_1,v_2\in B_1^*$ and $w_1,w_2\in B_2^*$. Furthermore, $\{e_1,e_2\}$ was a $2$-edge-separator in $B$. Thus, $B_1^*$ and $B_2^*$ are connected as $B$ is $2$-edge-connected. Let $B_1$ be obtained from $B_1^*$ by adding an edge $e_3=\{v_1,v_2\}$ and marking $e_3$. Note that $B_1$ is also strongly embeddable on $\torus{g_1}$. We claim that $B_1$ is $2$-connected. Indeed, any path in $B$ between vertices in $B_1$ gives rise to a path in $B_1$ between the same vertices by replacing any sub-path in $B\setminus B_1$ by the edge $e_3$. Thus, $B_1$ is $2$-connected as $B$ is. Analogously, we add the edge $e_4=\{w_1,w_2\}$ to $B_2^*$ to obtain a $2$-connected multigraph $B_2$ strongly embeddable on $\torus{g_2}$. We also mark $e_4$. Furthermore, we claim that both $B_1$ and $B_2$ cannot have facewidth 1. Indeed, suppose that $B_1$ has facewidth $1$ for a certain embedding $M_1$, then we can perform the reverse direction of the surgery to get an embedding of $B$. Since $B$ is of facewidth at least $2$, the only possibility is that the face containing the essential circle of length $1$ in $M_1$ is one of those created in the surgery from $B$ to $B_1$ and $B_2$, which is not possible by construction. Therefore, $B_1$ has facewidth at least $2$, and analogously, $B_2$ has facewidth at least two as well. Therefore, in this case, we can conclude that a multigraph $B$ can be constructed from a $2$-connected multigraph embeddable on $\torus{g'}$ with one marked edge and a $2$-connected multigraph embeddable on $\torus{g-g'}$ with one marked edge, with both multigraphs of facewidth at least $2$, resulting in the term \begin{equation*} \sum_{g'=1}^{g-1}\opb{y}{z}\br{\vertex{\two_{g'}}^{\fw \geq 2}(x,y,z)}\opb{y}{z}\br{\vertex{\two_{g-g'}}^{\fw \geq 2}(x,y,z)}. \end{equation*} Note that $e_3$ and $e_4$ might be single edges or part of double edges. Therefore, differentiating with respect to both possibilities results in an upper bound. The factor $\br{\frac{1}{y}+\frac{y}{z}}^2$ accounts for the deletion of $e_1$ and $e_2$, each of which might have been a single edge or part of a double edge (hence deleting it turns a double edge into a single edge). The factor $\br{y+\frac{z}{y}}^2$ represents the insertion of $e_3$ and $e_4$, each of which either adds a single edge or turns a single edge into a double edge. Both factors contribute to the the upper bound as they overcount. Furthermore, we obtain a factor of two for the ways to obtain the original multigraph from $B_1$ and $B_2$. \emph{Case 2:} Cutting along $C$ does not disconnect the surface. As the embedding after cutting is still a $2$-cell embedding, $B\setminus\{e_1,e_2\}$ is connected. We can connect $v_1$, $v_2$, $w_1$, $w_2$ in $B\setminus\{e_1,e_2\}$ by two edges (without loss of generality $e_3=\{v_1,v_2\}$ and $e_4=\{w_1,w_2\}$) so as to obtain a multigraph $B^*$. The graph $\ol{B}=B\cup\{e_3,e_4\}$ has a $2$-cell embedding $\ol{M}$ on $\Sg$ such that $e_1\cup e_2\cup e_3\cup e_4$ bounds a face. Indeed, starting from $M$, $e_3$ and $e_4$ can be embedded so that they run close to $e_1$, $e_2$, and $C$. Let $M^*$ be the embedding of $B^*$ induced by $\ol{M}$. Suppose that $B^*$ is not $2$-connected, that is, it has a bridge $e$. Note that $e$ cannot be $e_3$ or $e_4$ as $B^*\setminus\{e_3,e_4\}=B\setminus\{e_1,e_2\}$ is connected. There is a (not necessarily essential) circle $C'$ on $\Sg$ hitting $M^*$ only in $e$. As $e$ has not been a bridge in $B$, $C'$ has to meet $e_1$ and $e_2$ as well. If it met neither $e_1$ nor $e_2$, it would either contradict $B$ having facewidth two (if $C'$ is essential) or the $2$-connectivity of $B$ (if $C'$ is not essential). If it met only one of them, it would have to meet one of $e_3$, $e_4$, because $e_1$, $e_2$, $e_3$ and $e_4$ bound a disk in $\ol{M}$. This contradicts the fact that $C'$ meets $M^*$ only in $e$. We now construct the circle $C''$ as follows. First, we follow $C'$ from $e$ to $e_1$ without traversing it. Then, we follow $e_1$ until reaching $C$ and switch to $C$ to reach $e_2$ without crossing $e_1$ and $e_2$. Finally, we return to $C'$ along $e_2$ and then return to $e$ (see \Cref{fig:newcurve}). $C''$ meets $M$ only in $e$. Either $C''$ is an essential circle, contradicting the fact that $B$ has facewidth two, or it is planar, contradicting the $2$-connectivity of $B$. Similarly, we can also prove that $B^*$ has facewidth at least $2$. Thus we conclude that every multigraph $B$, where the surgery does not result in disconnecting the surface, can be constructed from a $2$-connected multigraph embeddable on $\mathbb{S}_{g-1}$ with two marked edges and facewidth at least two, which results in the term \begin{equation*} \opb{y}{z}^2\vertex{\two_{g-1}}(x,y,z). \end{equation*} The factor $2\br{y+\frac{z}{y}}^2\br{\frac{1}{y}+\frac{y}{z}}^2$ follows as in Case $1$. We thus conclude \eqref{eq:2-conn-graphs-fw2}. \begin{figure}[htbp] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=2.0cm,y=2.0cm,scale=0.85] \clip(-0.5,-3.) rectangle (6.5,0.5); \draw [shift={(3.,-11.5)},color=black] plot[domain=1.2490457723982544:1.892546881191539,variable=\t]({9.486832980505138*cos(\t r)+0.*9.486832980505138*sin(\t r)},{0.*9.486832980505138*cos(\t r)+9.486832980505138*sin(\t r)}); \draw [shift={(3.,9.)},color=black] plot[domain=4.3906384259880475:5.034139534781332,variable=\t]({9.486832980505138*cos(\t r)+0.*9.486832980505138*sin(\t r)},{0.*9.486832980505138*cos(\t r)+9.486832980505138*sin(\t r)}); \draw [color=black] (0.,-0.5)-- (1.,-0.75); \draw [color=black] (0.,-1.)-- (1.,-0.75); \draw [color=black] (1.,-0.75)-- (5.,-0.75); \draw [color=black] (5.,-0.75)-- (6.,-0.5); \draw [color=black] (5.,-0.75)-- (6.,-1.); \draw [color=black] (0.,-1.5)-- (1.,-1.75); \draw [color=black] (1.,-1.75)-- (0.,-2.); \draw [color=black] (1.,-1.75)-- (5.,-1.75); \draw [color=black] (5.,-1.75)-- (6.,-1.5); \draw [color=black] (5.,-1.75)-- (6.,-2.); \draw [color=red, very thick] (1.52,-0.7)-- (2.81,-0.7); \draw [color=red, very thick] (1.52,-1.8)-- (2.81,-1.8); \draw[color=orange](2.81,-0.7) arc (134:226:0.5266143949538169cm and 1.5268229493056935cm); \draw[color=red,very thick](2.9990944015573464,-0.48640228565126853) arc (90:134:0.5266143949538169cm and 1.5268229493056935cm); \draw[color=red,very thick](2.81,-1.8) arc (226:270:0.5266143949538169cm and 1.5268229493056935cm); \draw[color=red,very thick,dash pattern=on 2pt off 2pt](2.9990944015573464,-2.013225234956962) arc (270:450:0.5266143949538169cm and 1.5268229493056935cm); \draw [samples=50,domain=-0.27:0.27,rotate around={179.94666265828377:(5.0469120090352,-1.2551517251060296)},xshift=10.0938240180704cm,yshift=-2.510303450212059cm,color=green] plot ({3.0469063708808277*(1+(\x)^2)/(1-(\x)^2)},{0.9466212588310281*2*(\x)/(1-(\x)^2)}); \draw [samples=50,domain=-0.5:-0.27,rotate around={179.94666265828377:(5.0469120090352,-1.2551517251060296)},xshift=10.0938240180704cm,yshift=-2.510303450212059cm,color=red, very thick] plot ({3.0469063708808277*(1+(\x)^2)/(1-(\x)^2)},{0.9466212588310281*2*(\x)/(1-(\x)^2)}); \draw [samples=50,domain=0.27:0.5,rotate around={179.94666265828377:(5.0469120090352,-1.2551517251060296)},xshift=10.0938240180704cm,yshift=-2.510303450212059cm,color=red, very thick] plot ({3.0469063708808277*(1+(\x)^2)/(1-(\x)^2)},{0.9466212588310281*2*(\x)/(1-(\x)^2)}); \draw [color=orange](2.7,-1.15) node[anchor=north west] {C}; \draw [color=green](1.7,-1.15) node[anchor=north west] {C'}; \draw [color=red](2,-0.43) node[anchor=north west] {C''}; \begin{scriptsize} \draw [fill=black] (1.,-0.75) circle (1.5pt); \draw[color=black] (1.0335548589070693,-0.620620382783603) node {$v_1$}; \draw [fill=black] (1.,-1.75) circle (1.5pt); \draw[color=black] (1.0384686251057282,-1.6279424535086915) node {$v_2$}; \draw [fill=black] (5.,-0.75) circle (1.5pt); \draw[color=black] (4.9301714544436654,-0.6451892137768979) node {$w_1$}; \draw [fill=black] (5.,-1.75) circle (1.5pt); \draw[color=black] (4.915430155847688,-1.6082873887140556) node {$w_2$}; \draw [fill=black] (0.,-0.5) circle (1.5pt); \draw [fill=black] (0.,-1.) circle (1.5pt); \draw [fill=black] (0.,-1.5) circle (1.5pt); \draw [fill=black] (0.,-2.) circle (1.5pt); \draw [fill=black] (6.,-0.5) circle (1.5pt); \draw [fill=black] (6.,-1.) circle (1.5pt); \draw [fill=black] (6.,-1.5) circle (1.5pt); \draw [fill=black] (6.,-2.) circle (1.5pt); \draw[color=black] (3.6305288734712478,-0.65) node {$e_1$}; \draw[color=black] (3.6305288734712478,-1.65) node {$e_2$}; \end{scriptsize} \end{tikzpicture} \caption{Finding an essential circle witnessing small facewidth}\label{fig:newcurve} \end{figure} To prove \eqref{eq:conn-graphs-fw1}, let $G$ be a multigraph in $\class{\one}_g^{\fw=1}$. We fix a $2$-cell embedding $M$ of $G$ on $\Sg$ of facewidth one and let $e_1=\{v_1,v_2\}$ be an edge such that there exists an essential circle $C$ on $\Sg$ meeting $G$ only in $e_1$. Then we perform the following surgery: we delete $e_1$, cut the surface along $C$, close both holes with a disk, and attach an edge, an additional vertex and a loop to both $v_1$ and $v_2$. Remark that the edge deleted may be a single edge or part of a double edge. Thus, we have a factor of $(xyw)^2\br{\frac1y+\frac yz}$, overcounting all possibilities. The deleted edge cannot be a loop, since in cubic maps on orientable surfaces loops are always on the boundary of two different faces, and as such cannot be the only intersection of an embedding of a multigraph with an essential circle. This can easily be seen, as there is only one other edge at the base of the loop. Thus, the boundary of the face of the loop without this additional edge consists only of traversing the loop once. By this surgery, we either disconnect the surface or we reduce its genus by one. If we separate the surface, we obtain two connected multigraphs each with one marked loop. These multigraphs are counted by $\opa{w}(\one_{g'})$ and by $\opa{w}(\one_{g-g'})$, as the genera of the two parts sum up to $g$ and the embeddings resulting from the surgery are still $2$-cell embeddings. If the surface is not separated, the resulting embedding is a $2$-cell embedding and hence the multigraph remains connected. Therefore, we obtain a multigraph counted by $\opa{w}^2(\one_{g-1})$. The factor in front of the generating function is once again obtained by marking two loops. This proves \eqref{eq:conn-graphs-fw1}. \end{proof} In subsequent calculations, it will be more convenient to change the differential operators to operators with respect to $x$ instead of $y$, $z$, and $w$. \begin{coro}\label{coro:small-fw} For $g\ge 1$, we have \begin{align} \vertex{\two_g}^{\fw=2}(x,&y,z) \preceq \frac{9}{2} \br{y+\frac{z}{y}}^2\br{\frac1y+\frac yz}^2 \bigg(\opa{x}^2\br{\vertex{\two_{g-1}^{\fw\ge2}}(x,y,z)}\nonumber\\ &+\sum_{g'=1}^{g-1}\opa{x}\br{\two_{g'}^{\fw\ge2}(x,y,z)}\opa{x}\br{\two_{g-g'}^{\fw\ge2} (x,y,z)}\bigg),\label{eq:2-conn-graphs-fw2-x} \end{align} and \begin{align} \vertex{\one_g}^{\fw=1}(x,&y,z,w)\preceq \br{xyw}^2\br{\frac1y+\frac yz}\bigg(\opa{x}^2\br{\vertex{\one_{g-1}} (x,y,z,w)}\nonumber\\ &+\sum_{g'=1}^{g-1}\opa{x}\br{\vertex{\one_{g'}}(x,y,z,w)}\opa{x}\br{\vertex{\one_{g-g'}}(x,y,z,w)}\bigg).\label{eq:conn-graphs-fw1-x} \end{align} \end{coro} \begin{proof} Since the generating function $\vertex{\two_g}^{\fw \geq 2}$ counts cubic graphs, it is the sum of monomials of the form $x^{2k}y^{3k-2\ell}z^{\ell}$ for some nonnegative integers $k, \ell$ with $2l\leq3k$. We thus have \[ \opa{x} x^{2k}y^{3k-2\ell}z^{\ell} = 2k x^{2k}y^{3k-2\ell}z^{\ell} \geq \frac{2}{3} (3k-\ell) x^{2k}y^{3k-2\ell}z^{\ell} = \frac{2}{3} \opb{y}{z} x^{2k}y^{3k-2\ell}z^{\ell}. \] Therefore, we have $\frac{3}{2} \opa{x} \vertex{\two_g}^{\fw \geq 2} \geq \opb{y}{z} \vertex{\two_g}^{\fw \geq 2}$. Combining this with \eqref{eq:2-conn-graphs-fw2} proves \eqref{eq:2-conn-graphs-fw2-x}. To show \eqref{eq:conn-graphs-fw1-x}, we note that a cubic graph has at most as many loops as vertices, and thus replacing $\opa{w}$ by $\opa{x}$ increases each coefficient. Thus, we still have an upper bound when replacing $\opa{w}$ by $\opa{x}$ in \eqref{eq:conn-graphs-fw1}. \end{proof} \Cref{coro:small-fw} will be used to show that the number of multigraphs with small facewidth in \Cref{conngf-bounds} is negligible. Additionally, we need equations for the generating functions of the auxiliary classes $\class N$ and $\class Q$. Recall that $\class{\network}$ is the class of edge-rooted 2-connected vertex-labelled cubic planar multigraphs, and $\class{Q}$ is the class of all edge-rooted connected vertex-labelled cubic planar multigraphs whose root edge is a loop. \begin{prop} The generating function $\vertex{\network}(x,y,z)$ of $\class{\network}$ satisfies the system of equations \begin{align} \begin{split} \vertex{\network}(x,y,z)&=\frac{u(1-2u)-x^2y(1+\network(x,y,z))(y^2-2z)}{2},\label{eq:network}\\ x^2y^3(1+\vertex{\network}(x,y,z))^3&=u(1-u)^3, \end{split} \end{align} and the generating function $\vertex{Q}(x,y,z,w)$ of $\class{Q}$ satisfies \begin{align} \begin{split} \vertex{Q}&=\frac{\vertex{Q}^2}{2}+\frac{x^2y^3}{2}\br{A+\ol{Q}}+x^2 y^2 w,\label{systemq}\\ \vertex{A}&=\vertex{Q}+\vertex{S}+\vertex{P}+\vertex{H},\\ \vertex{S}&=\frac{\vertex{A}^2}{\vertex{A}+1},\\ \vertex{P}&=\frac{x^2y^3}{2}\vertex{A}^2+x^2y^3\vertex{A}+x^2yz,\\ 2\vertex{H}(1+\vertex{A})&=u(1-2u)-u(1-u)^3,\\ x^2y^3\vertex{A}^3&=u(1-u)^3, \end{split} \end{align} where \begin{equation*} \ol{Q}= \begin{cases} -Q\qquad&\text{for simple graphs,}\\ 0&\text{for weighted multigraphs,}\\ Q\qquad&\text{for multigraphs.} \end{cases} \end{equation*} \end{prop} \begin{proof} We obtain \eqref{systemq} by following the lines of Section $3$ in \cite{kang2012} or Section $3$ in \cite{Noy2012-probability-of-planarity}. The only difference is that we account for loops and double edges in the initial conditions. In order to derive the system for $Q$, one starts with an edge-rooted connected cubic planar graph and recursively decomposes it depending on the placement of the root. One of the following mutually exclusive cases occurs: \begin{enumerate} \item\label{planar:q} the root is a loop; \item\label{planar:d} the root is a bridge; \item\label{planar:s} the root is part of a minimal separating edge set of size two; \item\label{planar:p} the end vertices of the root separate the graph; or \item\label{planar:h} the root is part of a $3$-connected component. \end{enumerate} In Case~\ref{planar:q} we obtain an equation for $Q$, while Case~\ref{planar:d} results in an equation that can immediately be eliminated from the system, Case~\ref{planar:s} in the equation for $S$, Case~\ref{planar:p} in the equation for $P$ and Case~\ref{planar:h} in the parametric equations for $H$ in terms of $u$. It is shown in \cite{kang2012} that these cases are indeed exhaustive. For each of these cases, there is a decomposition of the graph resulting in the corresponding equation in the system. The difference for the three values of $\ol{Q}$ is due to the difference of how to deal with loops and double edges in the three different weightings. The only difference in the systems of all three weightings comes from Case~\ref{planar:q}, when the third edge at the root vertex is incident to a double edge (see \Cref{Qbar}). While this case cannot happen for simple graphs (and thus it is not possible to obtain a loop as a root in this case), the difference regarding weighted and unweighted multigraphs is due to the weighting of $\frac{1}{2}$ of the double edge. \begin{figure}[htbp] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm,scale=1] \tikzset{myptr/.style={decoration={markings,mark=at position 1 with {\arrow[scale=3,>=stealth]{>}}},postaction={decorate}}} \draw(0.,0.)--(1,0); \draw(3,0.)--(4,0); \draw[fill=black](4.4,0.)circle (.4pt); \draw[fill=black](4.5,0.)circle (.4pt); \draw[fill=black](4.6,0.)circle (.4pt); \draw[fill=black](0.,0.)circle (1.5pt); \draw[fill=black](1.,0.)circle (1.5pt); \draw[fill=black](3.,0.)circle (1.5pt); \draw (1,0.) to[out=30,in=150](3,0); \draw (1,0.) to[out=330,in=210](3,0); \draw (0,0.) to[out=100,in=90](-1,0); \draw (-1,0.) to[out=270,in=260](0,0); \draw[myptr](-0.02,-0.03)--(0,0); \end{tikzpicture} \caption{The exceptional case which has to be dealt with differently for simple graphs, weighted and unweighted multigraphs.}\label{Qbar} \end{figure} To obtain the equations for $\network(x,y,z)$, we start with \eqref{systemq}. Because $\network(x,y,z)$ enumerates edge-rooted $2$-connected planar cubic multigraphs, setting $w=0$ and $Q(x,y,z,w)=0$ results in a system of equations for $\network(x,y,z)=1+A$. The given equations follow by eliminating $S$, $P$, and $H$ from the new system. \end{proof} \subsection{Asymptotics}\label{sec:asy} The goal of this section is to obtain asymptotics for $\one_g(v)$ via \Cref{conngf-bounds}. The analysis for $\one_g^u(v)$ and $\one_g^s(v)$ are analogous; we will point out the differences when they occur. To use \Cref{conngf-bounds}, we will prove asymptotic formulas for each of the occurring terms. In order to simplify notations, we define \begin{equation*} \widetilde{\three}_g(x,y,z,w)=\three_g\left(x, \oy\left(1+\network(x, \oy, \oz)\right)\right), \end{equation*} where \begin{equation*} \oy = \frac{y}{1-Q(x,y,z,w)}, \quad\text{and } \quad \oz = \frac{1}{2} \left( \frac{y}{1-Q(x,y,z,w)} \right)^2 - \frac{y^2}{2} + z. \end{equation*} This change of variables comes from \Cref{conngf}. Facewidth conditions can be added in the usual way. Additionally, we define \begin{align*} \widetilde{\network}(x,y,z,w)&=\network\left(x, \oy,\oz\right)\\ \widetilde{\two}_g(x,y,z,w)&=\two_g\left(x, \oy,\oz\right). \end{align*} Furthermore, when writing $v$ as the sole variable, we are always using the corresponding substitution from \Cref{def:univariate}. In order to determine the dominant singularity of $\widetilde{\three}_g^{\fw\ge3}(v)$, one of the summands in \Cref{conngf-bounds}, we first analyse the dominant singularity of $Q(v)$. The numerical values of the dominant singularities and other constants are different for $Q(v)$, $Q^u(v)$, and $Q^s(v)$, but the analysis works in exactly the same way. \begin{lem}\label{planarconn} The dominant singularity of $Q(v)$ is $\rho_Q=\frac{54}{79^{3/2}}$. Furthermore, $Q(v)$ is $\Delta$-analytic and \[Q(v) \cong q_0(1-\rho_Q^{-1}v)^{3/2}+O\br{(1-\rho_Q^{-1}v)^2},\] where $q_0$ is a constant and we have $Q(\rho_Q) =1-\frac{17}{2\sqrt{79}}$. \end{lem} \begin{proof} Substituting $v$ as in \Cref{def:univariate} in \eqref{systemq} and eliminating $\vertex{S}$, $\vertex{P}$, $\vertex{H}$, $u$, and $\vertex{A}$ in this order from \eqref{systemq}, we get the following implicit equation for $\vertex{Q}$. \begin{align} \begin{split}\label{implicit:Q} 0=&256 Q^4 - 512 Q^5 + 384 Q^6 - 128 Q^7 + 16 Q^8 \\+&v(-320 Q^3 - 224 Q^4 + 2352 Q^5 - 3304 Q^6 + 2008 Q^7 - 576 Q^8 + 64 Q^9) \\+&v^2 (144 Q^2 + 136 Q^3 - 384 Q^4 + 210 Q^5 - 35 Q^6)\\+&v^3 (-28 Q + 42 Q^2 - 14 Q^3) + 2 v^4. \end{split} \end{align} Using standard methods for implicitly defined functions (see for example \cite[VII.7.1]{Flajolet2009-analytic-combinatorics}), we determine the dominant singularity to be at $\rho_Q=\frac{54}{79^{3/2}}$ and obtain the stated expression for $Q(v)$ and the value of $Q(v)$ at $\rho_Q$. \end{proof} This lemma is already strong enough to deal with the planar case. By unrooting the classes in \Cref{planarconn}, we obtain the asymptotic expansion of $\one_0(v)$ as a corollary. \begin{coro} \label{coro:conn-planar} The dominant singularity of the generating function $\vertex{\one_0}(v)$ of planar connected cubic vertex-labelled weighted multigraphs is $\rho_{Q}=\frac{54}{79^{3/2}}$. Furthermore, the generating function $\one_0(v)$ is $\Delta$-analytic and \begin{align*} \vertex{\one}_0(v)= & a_0+a_1\left( 1 - \rho_{\one}^{-1} v \right)+a_2\left( 1 - \rho_{\one}^{-1}v \right)^2 \\ &+c_0\left( 1 - \rho_{\one}^{-1} v\right)^{5/2}+O\br{\left( 1 - \rho_{\one}^{-1} v \right)^3}, \end{align*} where $c_0$, $a_0$, $a_1$, $a_2$ are constants. \end{coro} \begin{proof} The class of planar connected cubic multigraphs is given by unrooting the sum of the classes used in \Cref{planarconn}. It is easy to see that all those classes have the same dominant singularity as $Q(v)$, see \cite{bodirsky2007-cubic-graphs,kang2012,noy2016random} for more details. \end{proof} Similar results also hold for unweighted multigraphs and simple graphs with the same dominant singularities as $Q^u(v)$ and $Q^s(v)$, respectively. Next we determine the asymptotic behaviour of networks in $\widetilde{\network}(v)$. The only difference to the other two cases are the numerical values of $n_0$ and $\widetilde{N}(\rho_N)$. \begin{lem}\label{planarnetwork} The dominant singularity of $\widetilde{\network}(v)$ occurs at $\rho_N=\rho_Q=\frac{54}{79^{3/2}}$. Furthermore, $\widetilde{\network}(v)$ is $\Delta$-analytic, and \[ \widetilde{\network}(v) \cong n_0\br{(1-\rho_N^{-1}v)^{3/2}} + O\br{(1-\rho_N^{-1}v)^2}, \] where $n_0$ is a constant and $\widetilde{N}(\rho_N) = 1/16$. \end{lem} \begin{proof} Starting from \eqref{eq:network}, we obtain a system of equations that is satisfied by $\widetilde{\network}(v)$ by performing the appropriate substitutions on $y$ and $z$ in \eqref{eq:network}: first $y=\oy$ and $z=\oz$, then the substitutions from \Cref{def:univariate}. We thus obtain a system of two equations involving $\widetilde{\network}(v)$, $u$, $v$ and $Q(v)$. We then add \eqref{implicit:Q}, relating $Q(v)$ and $v$, and obtain a determined system. Eliminating $Q(v)$ and $u$ from this system results in an implicit equation in $\widetilde{N}(v)$ and $v$. Using standard methods (see for example \cite[VII.7.1]{Flajolet2009-analytic-combinatorics}) to deal with implicitly defined functions we determine the dominant singularity to be at $\rho_N=\rho_Q$ and derive the claimed properties of $\widetilde{N}(v)$. \end{proof} With the help of these two lemmas we obtain the singularity and singular expansion of the main term $\widetilde{\three}_g^{\fw\ge3}(v)$ in \Cref{conngf-bounds}. \begin{lem}\label{lem:3conn-subs} The generating function $\widetilde{\vertex{\three}}_g^{\fw \geq 3}(v)$ has its dominant singularity at $\rho_{\three}=\rho_Q=\frac{54}{79^{3/2}}$. Furthermore, we have \begin{align*} \widetilde{\vertex{\three}}_0(v) &\cong c_0 (1-\rho_Q)^{5/2} + O\br{(1-\rho_Q)^3},\\ \widetilde{\vertex{\three}}_1^{\fw \geq 3}(v) &\cong c_1 \log(1-\rho_Q^{-1}v) + O\br{(1-\rho_Q^{-1}v)^{1/4}},\\ \widetilde{\vertex{\three}}_g^{\fw \geq 3}(v) &\cong c_g (1-\rho_Q^{-1}v)^{-5g/2+5/2}+O\br{(1-\rho_Q^{-1}v)^{-5g/2+11/4}} \quad\text{for }g\ge2. \end{align*} \end{lem} Analogous results to \Cref{lem:3conn-subs} also hold for unweighted multigraphs and simple graphs. The only difference are the numerical values of the constants and the dominant singularities, where the latter coincide with the dominant singularities of $Q^u(v)$ and $Q^s(v)$, respectively. \begin{proof} The dominant singularity of $\widetilde{\vertex{\three}}_g^{\fw \geq 3}(v)$ is given either by the singularity $\rho_Q$ of $Q(v)$ and $\widetilde{N}(v)$, or by a solution of $\frac{v(1+\widetilde{N}(v))^3}{(1-Q(v))^3} = \rho_S^3$, where $\frac{v(1+\widetilde{N}(v))^3}{(1-Q(v))^3}$ is obtained by substituting $v$ in $x^2 (\oy(1+N(x,\oy,\oz)))^3$, and $\rho_S^3$ is the dominant singularity of $D_g(v)$. By \Cref{simplerefined} and \Cref{planarnetwork} we verify that $\frac{\rho_Q(1+\widetilde{N}(\rho_Q))^3}{(1-Q(\rho_Q))^3} = \rho_S^3$. This is the only solution of this equation, as $\frac{v(1+\widetilde{N}(v))^3}{(1-Q(v))^3}$ is a power series with positive coefficients, and thus monotone on the interval $[0, \rho_Q)$. Therefore, the dominant singularity of $\widetilde{\vertex{\three}}_g^{\fw \geq 3}(v)$ is $\rho_Q$, and the composition is critical (in the sense of \cite[pp. 411ff]{Flajolet2009-analytic-combinatorics}). We thus conclude the proof by \Cref{coro:3-conn-graphs}, and noting that $D_g^{\fw \geq 3}(v)$ has same asymptotic behaviour as $D_g(v)$. \end{proof} The next lemma shows the asymptotic behaviour of $\widetilde{\vertex{\two}}_g^{\fw =2}(v)$, which is the next term occurring in the bounds of \Cref{conngf-bounds}. \begin{lem} \label{coro:2conn-subs} For $g \geq 1$, we have \begin{equation}\label{eq:fw2small} \widetilde{\two}_g^{\fw=2}(v) \cong O\br{\br{1-\rho_{\network}^{-1} v}^{-5g/2+11/4}}. \end{equation} \end{lem} \begin{proof} First we observe that by \Cref{2conngf,lem:3conn-subs}, the generating function $\widetilde{\vertex{\two}}_g^{\fw \geq 3}(v)$ has its dominant singularity at $\rho_{\two}=\rho_Q=\frac{54}{79^{3/2}}$. Furthermore, \begin{align*} \widetilde{\vertex{\two}}_1^{\fw \geq 3}(v) &\cong c_1 \log(1-\rho_Q^{-1}v) + O\br{(1-\rho_Q^{-1}v)^{1/4}},\\ \widetilde{\vertex{\two}}_g^{\fw \geq 3}(v) &\cong c_g (1-\rho_Q^{-1}v)^{-5g/2+5/2} + O\br{(1-\rho_Q^{-1}v)^{-5g/2+11/4}} \quad\text{for }g\ge2. \end{align*} We prove the claim by induction on $g$. Suppose that our claim is correct for all $g' < g$. By \Cref{coro:small-fw} and the fact that both $\oy$ and $\oz$ are formal power series with positive coefficients, we have \begin{align} \begin{split}\label{eq:fw2foruse} \vertex{\two_g}^{\fw=2}\br{x,\oy,\oz}&\preceq \frac{9}{2} \br{\oy+\frac{\oz}{\oy}}^2\br{\frac{1}{\oy}+\frac{\oy}{\oz}}^2 \br{\opa{x}^2\vertex{\two_{g-1}^{\fw\ge2}}\br{x,\oy,\oz}}\\ &+\sum_{g'=1}^{g-1} \opa{x}\vertex{\two_{g'}^{\fw\ge2}}\br{x,\oy,\oz} \opa{x}\vertex{\two_{g-g'}^{\fw\ge2}}\br{x,\oy,\oz}. \end{split} \end{align} We now perform the substitutions as in \Cref{def:univariate}. Note that $x$ is substituted by $v^{1/4}$, while $\oy$ and $\oz$ are formal power series in $x,y,z,w$, all substituted by positive powers of $v$. Therefore, we can replace $\opa{x}$ by $4\opa{v}$ while keeping an upper bound. We thus have \begin{align}\label{eq:twoupper} \widetilde{\two}_g^{\fw=2}(v)\preceq 648 \left(\opa{v}^2(\widetilde{\two}_{g-1}^{\fw\ge2}(v))+\sum_{g'=1}^{g-1} \opa{v}(\widetilde{\two}_{g'}^{\fw\ge2}(v))\opa{v}(\widetilde{\two}_{g-g'}^{\fw\ge2}(v))\right). \end{align} The precise coefficient may change for unweighted multigraphs or simple graphs. By \Cref{integrating} and the fact that all generating functions on the right-hand side of \eqref{eq:twoupper} are for genus smaller than $g$, we deduce by induction that \begin{align*} \opa{v}^2(\widetilde{\two}_{g-1}^{\fw\ge2}(v))&\cong O\br{\br{ 1 - \rho_{\two}^{-1} v}^{-5g/2+3}}, \\ \opa{v}(\widetilde{\two}_{g'}^{\fw\ge2}(v))&\cong O\br{\br{ 1 - \rho_{\two}^{-1} v}^{-5g'/2+3/2}}, \\ \opa{v}(\widetilde{\two}_{g-g'}^{\fw\ge2}(v))&\cong O\br{\br{ 1 - \rho_{\two}^{-1} v}^{-5(g-g')/2+3/2}}. \end{align*} Substituting these congruences into \eqref{eq:twoupper} results in \begin{equation*} \widetilde{\two}_g^{\fw=2}(v)\preceq O\br{\br{ 1 - \rho_{\two}^{-1} v}^{-5g/2+3}}, \end{equation*} which immediately implies \eqref{eq:fw2small}. For the base case $g=1$, the computation is the same, except that we have a term $\opa{v}^2 \widetilde{\two}_0(v)$, which is $\opa{v}^2 \one_0(v)$, since $\two_0(x,\oy,\oz) = \one_0(x,y,z,w)$. By \Cref{coro:conn-planar}, we have \begin{equation*} \opa{v}^2 \widetilde{\two}_0(v) \cong a_2 + O\br{(1-\rho_Bv)^{1/2}}, \end{equation*} completing the proof. \end{proof} We use the asymptotic results in \Cref{coro:conn-planar}, \Cref{lem:3conn-subs}, and \Cref{coro:2conn-subs} to examine the bounds in \Cref{conngf-bounds} and determine the dominant term of connected cubic multigraphs embeddable on $\Sg$. \begin{thm}\label{thm:connected} For $g \geq 1$, the dominant singularity of the generating function $\vertex{\one_g}(v)$ of connected cubic vertex-labelled weighted multigraphs that are strongly embeddable on $\Sg$ is $\rho_{\one}=\rho_{Q}=\frac{54}{79^{3/2}}$. Furthermore, we have \begin{align*} \vertex{\one}_1(v)&\cong c_1\log\left( 1 - \rho_{\one}^{-1} v\right)+O\br{\left( 1 - \rho_{\one}^{-1}v \right)^{1/4}},\\ \vertex{\one}_g(v)&\cong c_g\left( 1 - \rho_{\one}^{-1} v \right)^{-5g/2+5/2}+ O\br{\left( 1 - \rho_{\one}^{-1} v \right)^{-5g/2+11/4}}\quad\text{for }g\ge 2, \end{align*} where $c_g$ is a constant depending only on $g$. \end{thm} \begin{proof} We first do the substitution of \Cref{def:univariate} in \eqref{eq:conngf-bounds}, which leads to \begin{align*} \widetilde{\vertex{\three}}_g^{\fw \geq 3}(v)& - \widetilde{\vertex{\three}}_0(v) + \widetilde{\vertex{\two}}_g^{\fw=2}(v) - \widetilde{\vertex{\two}}_0(v) + \vertex{\one}_g^{\fw=1}(v) \\ &\preceq \vertex{\one_g}(v) \preceq \widetilde{\vertex{\three}}_g^{\fw \geq 3}(v) + \widetilde{\vertex{\two}}_g^{\fw=2}(v) + \vertex{\one_g}^{\fw=1}(v). \end{align*} Comparing the terms other than $C_g^{\fw=1}(v)$ in these bounds, we obtain by \Cref{coro:conn-planar}, \Cref{lem:3conn-subs}, and \Cref{coro:2conn-subs} that the dominant term is $\widetilde{\vertex{\three}}_g^{\fw \geq 3}(v)$, which has the claimed singularity and decomposition. To conclude the proof, it remains to show that \begin{equation}\label{eq:fw1small} \vertex{\one_g}^{\fw=1}\cong O\br{\br{ 1 - \rho_{\one}^{-1} v}^{-5g/2+11/4}}. \end{equation} By \Cref{coro:small-fw} and the fact that by replacing $\opa{x}$ by $4\opa{v}$, the coefficients do not decrease, we have the relation \begin{align}\label{eq:oneupper} \one_g^{\fw=1}(v)\preceq \frac{27}{4}\opa{v}^2(\one_{g-1}(v))+\frac{27}{4}\sum_{g'=1}^{g-1} \opa{v}(\one_{g'}(v))\opa{v}(\one_{g-g'}(v)). \end{align} By the fact that all generating functions on the right-hand side of \eqref{eq:oneupper} are for genus smaller than $g$, we can use induction on $g$ as in the proof of \Cref{coro:2conn-subs} to deduce \eqref{eq:fw1small}, concluding the proof. \end{proof} From \Cref{thm:connected} and \Cref{congruent:tt}, we can immediately evaluate the coefficients of $\vertex{\one}_g(v)$. \begin{coro}\label{coro:gf-conn} The asymptotic number of connected cubic vertex-labelled multigraphs that are weighted by their compensation factor and are strongly embeddable on $\Sg$ is given by \begin{align*} [v^n]\vertex{\one_g}(v)&=\br{1+O\br{n^{-1/4}}} c_gn^{5g/2-7/2}\rho_{\one}^{-n}. \end{align*} Here $\rho_{\one}=\rho_Q=\frac{54}{79\sqrt{79}}$ and $c_g$ is a constant only depending on $g$. \end{coro} Again, both \Cref{thm:connected} and \Cref{coro:gf-conn} work analogously for unweighted multigraphs and simple graphs with different constants and dominant singularities of $Q^u(v)$ and $Q^s(v)$, respectively. \subsection{Proof of Theorem \ref{main2}} Using the results from \Cref{sec:asy} we can now prove \Cref{main2}. Recall that a cubic multigraph embeddable on $\Sg$ is given by a set of connected cubic multigraphs embeddable on $\torus{g_i}$ such that $\sum g_i\leq g$ (see \Cref{strongemb}). Therefore, we have the relation \begin{align} \vertex{\general}_g(v)&\preceq\sum_{k=1}^\infty\sum_{\sum g_i\le g}\frac{1}{k!}\prod_{i=1}^k\br{\vertex{\one}_{g_i}(v)+\frac{v}{6}}.\label{eq:all} \end{align} The summand $\frac{v}{6}$ accounts for the fact that a component might also be a triple edge, which is not taken into account in $\vertex{\one}_{g_i}(v)$ (this additional summand will differ when proving \Cref{main1,main3}). We only get an upper bound, because we overcount if a multigraph is strongly embeddable on surfaces of multiple genera. Later we will also obtain a lower bound with the same asymptotics to complete the proof. If $g=0$, the relation \eqref{eq:all} simplifies to $\general_0=\exp(\one_0+\frac{v}{6})$, as there is no overcounting in this case. This coincides with Theorem 1 of \cite{kang2012} and therefore we can conclude our statement in this case. (Although it is not directly shown there, the same arguments can be used for unweighted planar cubic multigraphs. For simple graphs, see \cite{bodirsky2007-cubic-graphs}.) Now suppose $g\ge 1$. The first step to obtain asymptotics from \eqref{eq:all} is to rearrange the sum in such a way that all planar components are singled out. This results in \begin{align}\label{eq:general:upperbound} \vertex{\general}_g(v)&\preceq\sum_{k=0}^g\sum_{\substack{\sum g_i\le g\\g_i\ge1}}\frac{1}{k!}\prod_{i=1}^k\br{\vertex{\one}_{g_i}(v)+\frac{v}{6}}\sum_{j=0}^\infty \frac{k!}{(k+j)!}\br{\vertex{\one}_0(v)+\frac{v}{6}}^j. \end{align} By the dominant term and the value of $\vertex{\one}_0(v)$ at the singularity $\rho_\one$ from \Cref{coro:conn-planar}, we observe that the last sum contributes only a constant factor. Thus, it remains to derive the dominant term of $\frac{1}{k!}\prod \br{\vertex{\one}_{g_i}(v)+\frac{v}{6}}$. As the first sum consists only of a constant number of summands, the dominant term of the right-hand side of \eqref{eq:general:upperbound} will be the (sum of the) dominant terms from $\frac{1}{k!}\prod \br{\vertex{\one}_{g_i}(v)+\frac{v}{6}}$ up to the constant obtained from the planar components. That is, we shall compute the dominant term of \begin{align*} A(v) := \frac{1}{k!}\prod_{i=1}^k\br{\one_{g_i}(v)+\frac{v}{6}}, \end{align*} where the $g_i$ are positive and sum up to $g'\le g$. For $g=1$, either $k=g'=0$ or $k=g'=1$. By \Cref{thm:connected}, we have \[A(v) = C_1(v)+\frac{v}{6}\cong c_1\log(1-\rho_{\one}^{-1}v)+\frac{v}{6}+O\br{\br{1-\rho_{\one}^{-1}v}^{1/4}}\] and thus \[A(v) \preceq P_1(v)+c_1\log(1-\rho_{\one}^{-1}v)+O\br{\br{1-\rho_{\one}^{-1}v}^{1/4}}\] with $P_1(v)$ a polynomial and $c_1$ a constant. Suppose now $g\ge 2$. Without loss of generality let $g_1,\ldots,g_l=1$ and let $g_{l+1}, \ldots,g_k>1$. Then \begin{align} \begin{split} A(v)\cong&\br{1+O\br{\br{1-\rho_{\one}^{-1}v}^{1/4}}}\frac{c_1^l}{k!} \left(\log\left(1-\rho_{\one}^{-1} v\right)\right)^l\label{eq:asys} \prod_{i=l+1}^kc_{g_i}\left( 1 - \rho_{\one}^{-1}v \right)^{5(1-g_i)/2}\\ \cong& \br{c+O\br{\br{ 1 - \rho_{\one}^{-1} v}^{1/4}}}\br{\log\left( 1 - \rho_{\one}^{-1} v\right)}^l \left( 1 - \rho_{\one}^{-1}v \right)^{-5g'/2+5k/2}. \end{split} \end{align} For $k=1$ and $g'=g$ (and hence $l=0$) we thus have \begin{align} \frac{1}{1!}\prod_{g'=1}^1\br{\one_{g_i}+\frac{v}{6}}\cong c_g(1-\rho_{\one}^{-1}v)^{-5g/2+5/2}+O\br{(1-\rho_{\one}^{-1}v)^{-5g/2+11/4}}.\label{eq:a} \end{align} For $k\ge2$ or $g'0$, which would yield a probability $1-O(n^{-5/2+\varepsilon})$. The statements of \Cref{main4} for unweighted multigraphs and simple graphs are proved analogously.\qed \begin{remark} Observe that the polynomials $p_1(u),p_3(u)$ whose smallest positive zeroes $u_1$ and $u_3$ give rise to the exponential growth constants $\gamma_1$ for cubic multigraphs and $\gamma_3$ for simple cubic graphs, respectively, satisfy the relation $p_1(u)=p_3(-u)$. It would be interesting to know whether this fact has a combinatorial meaning. \end{remark} \section{Acknowledgement} We thank the authors of \cite{noy2016random} for pointing out a mistake in an earlier version of this paper. We also thank the anonymous referee for very helpful suggestions on simplifying the proofs and presentation of the paper. \begin{thebibliography}{10} \bibitem{BENDER1986244} E.~A. Bender and E.~R. Canfield. \newblock The asymptotic number of rooted maps on a surface. \newblock {\em J. Combin. Theory Ser. A}, 43(2):244--257, 1986. \bibitem{Bender1993-maps} E.~A. Bender, E.~R. Canfield, and L.~B. Richmond. \newblock The asymptotic number of rooted maps on a surface. {II}. {E}numeration by vertices and faces. \newblock {\em J. Combin. Theory Ser. A}, 63(2):318--329, 1993. \bibitem{bendergao} E.~A. Bender and Z.~Gao. \newblock Asymptotic enumeration of labelled graphs by genus. \newblock {\em Electron. J. Combin.}, 18(1):\#P13, 2011. \bibitem{representativity} E.~A. Bender, Z.~Gao, and L.~B. Richmond. \newblock Almost all rooted maps have large representativity. \newblock {\em J. Graph Theory}, 18(6):545--555, 1994. \bibitem{bender} E.~A. Bender, Z.~Gao, and N.~C. Wormald. \newblock The number of labeled 2-connected planar graphs. \newblock {\em Electron. J. Combin.}, 9(1):\#R43, 2002. \bibitem{Bender1988370} E.~A. Bender and N.~C. Wormald. \newblock The asymptotic number of rooted nonseparable maps on a surface. \newblock {\em J. Combin. Theory Ser. A}, 49(2):370--380, 1988. \bibitem{Bodirsky08} M.~Bodirsky, C.~Gr\"opl, and M.~Kang. \newblock Generating unlabeled connected cubic planar graphs uniformly at random. \newblock {\em Random Structures Algorithms}, 32(2):157--180, 2008. \bibitem{bodirsky2007-cubic-graphs} M.~Bodirsky, M.~Kang, M.~L\"offler, and C.~McDiarmid. \newblock Random cubic planar graphs. \newblock {\em Random Structures Algorithms}, 30(1-2):78--94, 2007. \bibitem{triang-disk} W.~G. Brown. \newblock Enumeration of triangulations of the disk. \newblock {\em Proc. London Math. Soc. (3)}, 14:746--768, 1964. \bibitem{Chapuy2011-enumeration-graphs-on-surfaces} G.~Chapuy, \'E. Fusy, O.~Gim\'enez, B.~Mohar, and M.~Noy. \newblock Asymptotic enumeration and limit laws for graphs of fixed genus. \newblock {\em J. Combin. Theory Ser. A}, 118(3):748--777, 2011. \bibitem{flajolet1990-transfer} P.~Flajolet and A.~Odlyzko. \newblock Singularity analysis of generating functions. \newblock {\em SIAM J. Discrete Math.}, 3(2):216--240, 1990. \bibitem{Flajolet2009-analytic-combinatorics} P.~Flajolet and R.~Sedgewick. \newblock {\em Analytic combinatorics}. \newblock Cambridge University Press, Cambridge, 2009. \bibitem{Gao1991-2-connected-projective} Z.~Gao. \newblock The number of rooted {$2$}-connected triangular maps on the projective plane. \newblock {\em J. Combin. Theory Ser. B}, 53(1):130--142, 1991. \bibitem{Gao1991-conn-triang} Z.~Gao. \newblock The number of rooted triangular maps on a surface. \newblock {\em J. Combin. Theory Ser. B}, 52(2):236--249, 1991. \bibitem{Gao1992-2-connected-surface} Z.~Gao. \newblock The asymptotic number of rooted {$2$}-connected triangular maps on a surface. \newblock {\em J. Combin. Theory Ser. B}, 54(1):102--112, 1992. \bibitem{Gao1993-pattern} Z.~Gao. \newblock A pattern for the asymptotic number of rooted maps on surfaces. \newblock {\em J. Combin. Theory Ser. A}, 64(2):246--264, 1993. \bibitem{MR1980342} Z.~Gao and N.~C. Wormald. \newblock Enumeration of rooted cubic planar maps. \newblock {\em Ann. Comb.}, 6(3-4):313--325, 2002. \bibitem{gimenez2009} O.~Gim\'enez and M.~Noy. \newblock Asymptotic enumeration and limit laws of planar graphs. \newblock {\em J. Amer. Math. Soc.}, 22(2):309--329, 2009. \bibitem{quadratic-method} I.~P. Goulden and D.~M. Jackson. \newblock {\em Combinatorial enumeration}. \newblock A Wiley-Interscience Publication. John Wiley \&\ Sons, Inc., New York, 1983. \newblock With a foreword by Gian-Carlo Rota, Wiley-Interscience Series in Discrete Mathematics. \bibitem{jansonea} S.~Janson, D.~E. Knuth, T.~{\L}uczak, and B.~Pittel. \newblock The birth of the giant component. \newblock {\em Random Structures Algorithms}, 4(3):231--358, 1993. \bibitem{rgraphs} S.~Janson, T.~{\L}uczak, and A.~Rucinski. \newblock {\em Random graphs}. \newblock Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. \bibitem{kang2012} M.~Kang and T.~{\L}uczak. \newblock Two critical periods in the evolution of random planar graphs. \newblock {\em Trans. Amer. Math. Soc.}, 364(8):4239--4265, 2012. \bibitem{kms17} M.~Kang, M.~Mo{\ss}hammer, and P.~Spr{\"u}ssel. \newblock Phase transitions in graphs on orientable surfaces. \newblock \arxiv{1708.07671}. \bibitem{ks} M.~Kang and P.~Spr{\"u}ssel. \newblock Symmetries of unlabelled planar triangulations. \newblock To appear in {\em Electron. J. Combin.} \bibitem{seminaronrg} M.~Karo{\'n}ski and Z.~Palka, editors. \newblock {\em Random graphs '85}, volume 144 of {\em North-Holland Mathematics Studies}. \newblock North-Holland Publishing Co., Amsterdam, 1987. \newblock Papers from the second international seminar on random graphs and probabilistic methods in combinatorics held at Adam Mickiewicz University, Pozna{\'n}, August 5--9, 1985, Annals of Discrete Mathematics, 33. \bibitem{mcdiarmid2005} C.~McDiarmid, A.~Steger, and D.~J.~A. Welsh. \newblock Random planar graphs. \newblock {\em J. Combin. Theory Ser. B}, 93(2):187--205, 2005. \bibitem{mohar-thomassen} B.~Mohar and C.~Thomassen. \newblock {\em Graphs on surfaces}. \newblock Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. \bibitem{Noy2012-probability-of-planarity} M.~Noy, V.~Ravelomanana, and J.~Ru\'e. \newblock On the probability of planarity of a random graph near the critical point. \newblock {\em Proc. Amer. Math. Soc.}, 143(3):925--936, 2015. \bibitem{noy2016random} M.~Noy, C.~Requil{\'e}, and J.~Ru{\'e}. \newblock Random cubic planar graphs revisited. \newblock {\em Electronic Notes in Discrete Mathematics}, 54:211--216, 2016. \bibitem{osthus} D.~Osthus, H.~J. Pr\"omel, and A.~Taraz. \newblock On random planar graphs, the number of planar graphs and their triangulations. \newblock {\em J. Combin. Theory Ser. B}, 88(1):119--134, 2003. \bibitem{robertson1990-representativity} N.~Robertson and R.~Vitray. \newblock Representativity of surface embeddings. \newblock In {\em Paths, flows, and {VLSI}-layout ({B}onn, 1988)}, volume~9 of {\em Algorithms Combin.}, pages 293--328. Springer, Berlin, 1990. \bibitem{titchmarsh1939theory} E.~C. Titchmarsh. \newblock {\em The theory of functions}. \newblock Oxford University Press, Oxford, 1958. \newblock Reprint of the second (1939) edition. \bibitem{tutte1962-planar-triangulations} W.~T. Tutte. \newblock A census of planar triangulations. \newblock {\em Canad. J. Math.}, 14:21--38, 1962. \bibitem{tutte1963-planar-maps} W.~T. Tutte. \newblock A census of planar maps. \newblock {\em Canad. J. Math.}, 15:249--271, 1963. \bibitem{whitney} H.~Whitney. \newblock Congruent {G}raphs and the {C}onnectivity of {G}raphs. \newblock {\em Amer. J. Math.}, 54(1):150--168, 1932. \end{thebibliography} \appendix \section{Proof of Theorems \ref{simplerefined} and \ref{essentialsimple}} \label{proof:gao} In this appendix, we compute the asymptotic numbers of triangulations in $\class\triangs_g$ and $\hat{\class\triangs}_g$, as stated in \Cref{simplerefined,essentialsimple}, respectively. Our proof follows the approach of \cite{BENDER1986244}. \subsection{Surgeries}\label{sec:def:surgery} When dealing with maps on $\Sg$ we will perform operations on the surfaces that are commonly known as \emph{cutting} and \emph{gluing}. In the course of these operations we will encounter \emph{surfaces with holes}. A \emph{surface with $k$ holes} is a surface $\Sg$ from which the disjoint interiors $D_1,\ldots,D_k$ of $k$ closed disks have been deleted. Each $D_i$ is called a \emph{hole}. Let $S$ be the disjoint union of finitely many orientable surfaces, at least one of them with holes, and suppose that $X$ and $Y$ are homeomorphic subsets of the boundary of $S$. By \emph{gluing $S$ along $X$ and $Y$} we mean the operation of identifying every point $x\in X$ with $f(x)$ for any fixed homeomorphism $f\colon X\to Y$. The identification of $X$ and $Y$ induces a surjection $\sigma$ from $S$ onto the resulting space $\tilde S$. We write $\tilde X$ for the subset $\sigma(X)=\sigma(Y)$ of $\tilde S$. We will glue along subsets in two particular situations: when $X$ and $Y$ are \begin{enumerate} \item\label{glue:twoholes} disjoint boundaries of holes of $S$, or \item\label{glue:zipp} sub-arcs of the boundary of the same hole that meet precisely in their endpoints. \end{enumerate} For \ref{glue:zipp}, we shall additionally assume that the homeomorphism $f\colon X\to Y$ induces the identity on $X\cap Y$. In either case, the space $\tilde S$ resulting from gluing along $X$ and $Y$ is again the disjoint union of finitely many orientable surfaces with holes, with the number of components being either the same or one less than that for $S$. The subset $\tilde X$ of $\tilde S$ is a circle in Case~\ref{glue:twoholes} and homeomorphic to the closed unit interval in Case~\ref{glue:zipp}. If $S$ has $k$ holes, then $\tilde S$ has $k-2$ holes in Case~\ref{glue:twoholes} and $k-1$ holes in Case~\ref{glue:zipp}. A special case of~\ref{glue:twoholes} is when one of the components of $S$ is a disk (i.e.\ a sphere with one hole) and $Y$ is its boundary. In this case, we say that we \emph{close the hole bounded by $X$ by inserting a disk}. If in addition we are given a map $M$ on $S$, then we will glue along $X$ and $Y$ only if either both of them are contained in a face (not necessarily the same face for $X$ and $Y$) or both are unions of the same number of vertices and the same number of edges of $M$. We also assume the homeomorphism $f\colon X\to Y$ to map vertices to vertices and edges to edges. Under these conditions, we obtain a map $\tilde M$ on $\tilde S$. The subset $\tilde X$ of $\tilde S$ is then either a subgraph of $\tilde M$ or a subset of a face of $\tilde M$. Observe that the surjection $\sigma\colon S\to\tilde S$ induces a bijection between the sets of corners of $M$ and of corners of $\tilde M$. We will refer to this bijection by saying that every corner of $M$ \emph{corresponds} to a corner of $\tilde M$. If $\tilde S$ is obtained from $S$ by gluing along $X$ and $Y,$ we also say that vice versa, $S$ is obtained from $\tilde S$ by \emph{cutting along $\tilde X$}. The operation of cutting along a circle or interval is well defined in the sense that if $\tilde S$ and $\tilde X$ are given, then $S$, $X$, and $Y$ are unique up to homeomorphism. If $S$ has more components than $\tilde S$, we call $\tilde X$ \emph{separating}. Cutting along a separating circle on $\Sg$ and closing the resulting holes by inserting disks will yield two surfaces $\torus{g_1},\torus{g_2}$ with $g_1+g_2=g$. Cutting along a non-separating circle and closing the holes by inserting disks reduces the genus by one. A combination of cutting and gluing surfaces along some subsets of their boundaries is called a \emph{surgery}. Again, if a map $\tilde M$ results from performing surgeries on a map $M$, then every corner of $\tilde M$ corresponds to a corner of $M$. \subsection{Quasi-triangulations} We begin with some notations. The \emph{valency} of a face $f$ in a map is the number of corners of $f$. We call a rooted map $M$ a \emph{quasi-triangulation} if all faces except the root face $f_r$ are bounded by triangles. Let $\class{\quasis}_g$ be the class of \emph{simple} quasi-triangulations and $\quasis_g(y,u)$ its generating function, where $y$ marks the number of edges, and $u$ marks the valency of $f_r$. Given an index set $I$ and an injective function $h\colon I \to F(M)\setminus\{f_r\}$, we call $M$ an \emph{$I$-quasi-triangulation with respect to $h$} if all faces in $F(M) \setminus \br{h(I)\cup\{f_r\}}$ are bounded by triangles. If in addition $f_r$ is also bounded by a triangle, we say that $M$ is an \emph{$I$-triangulation} (with respect to $h$). Let $\class{\triangs}_{g,I}$ and $\class{\quasis}_{g,I}$ be the classes of simple $I$-triangulations and simple $I$-quasi-triangulations, respectively, with their generating functions denoted by $\triangs_g(y,z_I)$ and $\quasis_g(y,u,z_I)$, respectively. Here $u$ again marks the valency of the root face $f_r$ and $z_I=(z_i)_{i\in I}$ is a set of variables indexed by $I$, where $z_i$ marks the valency of $h(i)$. Additionally, let $\hat{\class{\quasis}}_g$, $\hat{\class{\triangs}}_{g,I}$, and $\hat{\class{\quasis}}_{g,I}$ be the analogous classes for triangulations without separating loops or separating double edges and $\hat{\quasis}_g(y,u)$, $\hat{\triangs}_g(y,z_I)$, and $\hat{\quasis}_g(y,u,z_I)$ their generating functions, respectively. Note that $\class{\triangs}_g=\class{\triangs}_{g,\emptyset}$ and $\class{\quasis}_g=\class{\quasis}_{g,\emptyset}$. In the case $I=\emptyset$, we will therefore always use the generating functions $\triangs_g(y)$ and $\quasis_g(y,u)$ without mentioning variables $z_i$. To simplify notations, the one-vertex map is put into $\class{\quasis}_0$, although it is not a quasi-triangulation, since it does not have any corners and thus cannot be rooted. We say that a face $f$ is \emph{marked} if $f\in h(I)$ and that we are \emph{marking a face} $f$ if we add a new index $i$ to the set $I$ with $h(i)=f$. We use the same convention also for the corresponding classes and generating functions for triangulations without loops and double edges. \bigskip To prove \Cref{simplerefined,essentialsimple}, we first derive a recursive formula relating $\class{\quasis}_{g,I}$ (and $\hat{\class{\quasis}}_{g,I}$) for different genera and different sizes of the set $I$. We then prove \Cref{simplerefined,essentialsimple} by applying this formula inductively. In order to derive the recursive formula, we delete the root edge of a given quasi-triangulation and then perform surgeries that either separate the given surface or decrease its genus. One part of the reverse operation then consists of adding a new edge to a map. Let $S$ be a map and $c_1=(v_1,e_1^-,e_1^+)$ and $c_2=(v_2,e_2^-,e_2^+)$ be two (not necessarily distinct) corners of the same face $f$ of $S$. For $T$ is a map with $V(T)=V(S)$ and $E(T) = E(S)\cup\{e_{\text{new}}\}$, we say that $e_{\text{new}}$ is an \emph{edge from $c_1$ to $c_2$} if \begin{itemize} \item $e_{\text{new}}$ is contained in $f$ and its end vertices are $v_1$ and $v_2$; \item in the cyclic order of edges of $T$ at $v_1$, $e_{\text{new}}$ is the predecessor of $e_1^+$; and \item in the cyclic order of edges of $T$ at $v_2$, $e_{\text{new}}$ is the successor of $e_2^-$. \end{itemize} If $c_1=c_2 =: c$, we also say that $e_{\text{new}}$ is a \emph{loop at $c$}. \subsection{The planar case} Before we derive the recursive formula, we first study the base case of \emph{planar} quasi-triangulations. \begin{prop}\label{prop:baseplanar} The generating function of planar quasi-triangulations satisfies \begin{align} \quasis_0(y,u)&=1+yu^2\quasis_0^2(y,u)+\frac{y(\quasis_0(y,u)-1)}{u}-y^2u\quasis_0(y,u)- \triangs_0(y)(\quasis_0(y,u)-1).\label{baseplanar} \end{align} Additionally, $\hat{\quasis}_0(y,u)=\quasis_0(y,u)$ holds. \end{prop} \begin{proof} As planar quasi-triangulations cannot have non-separating loops or double edges, $\hat{\quasis}_0(y,u)=\quasis_0(y,u)$ follows immediately. The first summand in \eqref{baseplanar} corresponds to the one-vertex map. Let $S\in\class{\quasis}_0$ be a planar quasi-triangulation with at least one edge. We distinguish two cases. First, suppose that the root edge $e_r$ is a bridge; then the only face incident with $e_r$ is the root face $f_r$. The union $f_r \cup e_r$ is not a disk and thus contains a non-contractible circle $C$. We delete $e_r$, cut along $C$, and close the two resulting holes by inserting disks. By this surgery, $S$ is separated into two quasi-triangulations $S_1$, $S_2$. Let $v_1$ and $v_2$ be the end vertices of $e_r$ in $S_1$ and $S_2$ respectively. One of these two vertices is the root vertex of $S$; by renaming $S_1,S_2$ we may assume that $v_1$ is the root vertex of $S$. In the cyclic order of the edges of $S$ at $v_1$, let $e_1^-$ and $e_1^+$ be the predecessor and successor of $e_r$ respectively. Define $e_2^-$ and $e_2^+$ analogously at $v_2$. We let $(v_1,e_1^-,e_1^+)$ and $(v_2,e_2^-,e_2^+)$ be the roots of $S_1$ and $S_2$ respectively. We thus have $S_1,S_2\in\class\quasis_0$. Furthermore, $S_1$ and $S_2$ together have one edge less than $S$ and the sum of the valencies of their root faces is two less than the valency of $f_r$. Thus, we obtain $yu^2\quasis_0^2(x,u)$, the second term of the right-hand side of \eqref{baseplanar}. Now suppose that $e_r$ is not a bridge. Then it lies on the boundary of the root face and of another face, which is bounded by a triangle. In the cyclic order of edges at the root vertex $v_r$, let $e_r^-$ and $e_r^+$ be the predecessor and successor of $e_r$, respectively. We delete $e_r$ and obtain a quasi triangulation $S'$ that we root at $c'_r:=(v_r,e_r^-,e_r^+)$. The valency of the root face of $S'$ is larger by one than the valency of $f_r$. This is reflected by $\frac{y}{u}(\quasis_0(y,u)-1)$, the third term of the right-hand side of \eqref{baseplanar}, because $S'$ cannot be the quasi-triangulation consisting only of a single vertex. However, with this summand we have overcounted. Indeed, the reverse construction is as follows. Let $f'_r$ be the root face of $S'$. Then the corners of $f'_r$ can be ordered by walking along the boundary of $f'_r$ in counterclockwise direction. In this order, starting from $c'_r$, let $c' = (v,e,e')$ be the corner after the next; then $S$ is obtained from $S'$ by inserting an edge from $c_r'$ to $c'$. If $v_r=v$ this results in a loop; if $v_r$ and $v$ are adjacent, we obtain a double edge (see \Cref{fig:planarquasi}). \begin{figure}[htbp] \centering \begin{tikzpicture} \draw [dash pattern=on 1pt off 1pt](3,2) to[out=130,in=0] (1.4,3)to[out=180,in=90] (0.8,2) to[out=270,in=180] (1.4,1) to[out=0,in=240] (3,2); \draw (1.8,2.)-- (3,2.); \draw [fill=gray](3,2) to[out=70,in=180] (5,3)to[out=0,in=90] (6,2) to[out=270,in=0] (5,1) to[out=180,in=290] (3,2); \draw [color=black](4.8,2) node {\Large $P_0$}; \draw (3,2) node[anchor=west] {$v_r=v$}; \draw [fill=gray](8.5,3)-- (8.5,1)-- (7.5,2.)-- (8.5,3); \draw [color=black](8.1,2) node {\Large $S_0$}; \draw [dash pattern=on 1pt off 1pt](8.5,3) to[out=190,in=90] (7,2) to[out=270,in=170](8.5,1); \draw [fill=gray](8.5,3) to[out=10,in=90] (10.7,2) to[out=270,in=350](8.5,1) -- (8.5,3); \draw [color=black](9.6,2) node {\Large $P_0$}; \draw [color=black](8.5,3.3) node {$v$}; \draw [color=black](8.5,0.7) node {$v_r$}; \begin{scriptsize} \draw [fill=black] (1.8,2.) circle (1.5pt); \draw [fill=black] (3,2.) circle (1.5pt); \draw [fill=black] (8.5,1) circle (1.5pt); \draw [fill=black] (8.5,3) circle (1.5pt); \draw [fill=black] (7.5,2.) circle (1.5pt); \end{scriptsize} \end{tikzpicture} \caption{Obtaining a loop or a double edge by inserting an edge.} \label{fig:planarquasi} \end{figure} These cases have to be subtracted again in order to obtain a valid formula. First suppose that $v_r=v$. As we do not have double edges in $S'$, this is only possible if the corner between $c_r'$ and $c'$ is at a vertex of degree one. We have to subtract $y^2u \quasis_0(y,u)$, i.e.\ the fourth term of the right-hand side of \eqref{baseplanar}, for this case (we add one vertex and two edges to a quasi-triangulation and increase the root face valency by one). Now suppose that $v_r$ and $v$ are adjacent, i.e. inserting an edge between them creates a double edge. In this case zipping the double edge separates the quasi-triangulation into two quasi-triangulations $S_1,S_2$. For one of them, without loss of generality for $S_1$, the root face valency is the same as for $S$, while the root face of $S_2$ has valency three. Thus, $S_1$ is in $\class{\quasis}_0$ but not the one-vertex map, while $S_2\in\class{\triangs}_0$. Summing up we have to subtract $\triangs_0(y)(\quasis_0(y,u)-1)$, the fifth term of the right-hand side of \eqref{baseplanar}. \end{proof} We can use the quadratic method (see e.g. \cite{quadratic-method}) to obtain the main result for planar triangulations from \Cref{prop:baseplanar}. Those were already obtained by Tutte \cite{tutte1962-planar-triangulations} with slightly different parameters. \begin{lem}\label{inductionbase} It holds that $\hat{\triangs}_0(y)=\triangs_0(y)$. The dominant singularity of $\triangs_0(y)$ is $\rho_\triangs=\frac{3}{2^{8/3}}$, $\triangs_0(y)$ is $\Delta$-analytic and satisfies \begin{align}\label{triangulations} \triangs_0(y)&=\frac{1}{8}-\frac{9}{16}\br{1-\rho_\triangs^{-1}y}+\frac{3}{2^{5/2}}\br{1-\rho_\triangs^{-1}y}^{3/2} +O\br{\br{1-\rho_\triangs^{-1}y}^{2}}. \end{align} Furthermore, for $u=f(y)$ with \begin{equation*}f(y)=\frac{t^{1/3}}{1+t}\quad\text{ and }\quad y=t^{1/3}(1-t),\label{simplesubstitution}\end{equation*} the equations \begin{align*} \quasis_0(y,f(y))&=\frac{5}{4}-\frac{3}{2^{5/2}}\br{1-\rho_\triangs^{-1}y}^{1/2}+O\br{1-\rho_\triangs^{-1}y},\\ \left.\br{\deriv{u}\quasis_0(y,u)}\right\vert_{u=f(y)}&= \frac{75}{2^{13/3}}-\frac{125\cdot 3^{3/4}}{2^{23/3}}\br{1-\rho_\triangs^{-1}y}^{1/4} +O\br{\br{1-\rho_\triangs^{-1}y}^{1/2}} \end{align*} hold and $\quasis_0(y,f(y))$ is $\Delta$-analytic. Let $n\ge 2$ be an integer. Then \begin{align*} \left.\br{\derivn{u}{n}\quasis_0(y,u)}\right\vert_{u=f(y)}=c(n)\br{1-\rho_\triangs^{-1}y}^{-n/2+3/4}+ O\br{\br{1-\rho_\triangs^{-1}y}^{-n/2+1}}, \end{align*} where $c(n)$ is a positive constant depending only on $n$. \end{lem} \begin{proof} As that planar quasi-triangulations cannot have non-separating loops or double edges, $\hat{\triangs}_0(y)=\triangs_0(y)$ follows immediately. Multiplying \eqref{baseplanar} by $4yu^4$ and rearranging the terms yields \begin{equation}\label{quadrat} \br{2yu^3\quasis_0(y,u)+q(y,u)}^2=q(y,u)^2+4y^2u^3-4yu^4-4yu^4\triangs_0(y), \end{equation} where $q(x,u)=y-y^2u^2-u-u\triangs_0(y)$. Let \begin{align*} Q(y,u)&=2yu^3\quasis_0(y,u)+q(y,u) &\text{and}&\\ R(x,u)&=q(y,u)^2+4y^2u^3-4yu^4-4yu^4\triangs_0(y). && \end{align*} Then \eqref{quadrat} reduces to $Q^2(y,u)=R(y,u)$. To obtain the claimed asymptotic behaviour one chooses $u=f(y)$ in such a way that $Q(y,f(y))=0$. This $u$ is a double zero of $Q^2(y,u)$ and therefore both $R(y,u)$ and $\deriv{u}R(y,u)$ are $0$ at $u=f(y)$, giving \begin{align*} 0&=q(y,u)^2+4y^2u^3-4yu^4-4yu^4\triangs_0(y),\\ 0&=2q(y,u)(1+\triangs_0(y)+2y^2u)+16y u^3+16y u^3\triangs_0(y)-12y^2u^2. \end{align*} By eliminating $f(y)$ from this system we obtain the implicit equation \begin{equation*} \triangs_0(y)^4 + 3 \triangs_0(y)^3+ \triangs_0(y)^2 (3 + 8 y^3) + \triangs_0(y) (1 - 20 y^3) = (1 - 16 y^3) y^3. \end{equation*} By standard methods for implicitly given functions (e.g.\ \cite[VII.7.1]{Flajolet2009-analytic-combinatorics}) we obtain the dominant singularity and the singular expansion of $\triangs_0(y)$ as stated in \eqref{triangulations}. Conversely, by eliminating $\triangs_0(y)$ and substituting $y=t^{1/3}(1-t)$ we obtain $f(y)=\frac{t^{1/3}}{1+t} = \frac{y}{1-t^2}$ and $\triangs_0(y)=t(1-2t)$. Since $\frac1{1-t^2}$ has only nonnegative coefficients in $t$ and $t=t(y)$ has only nonnegative coefficients by Lagrange Inversion, $f(y)$ has only nonnegative coefficients as well. From the implicit equation for $f(y)$ we deduce that \begin{equation} f(y)=\frac{2^{4/3}}{5}-\frac{2^{11/6}}{25}\br{1-\rho_\triangs^{-1}y}^{1/2}+O\br{1-\rho_\triangs^{-1}y}.\label{asyy} \end{equation} From $2yf(y)^3\quasis_0(y,f(y))+q(y,f(y)) = Q(y,f(y)) = 0$, \eqref{triangulations}, \eqref{asyy}, and $y = \rho_{\triangs}-\rho_{\triangs}(1-\rho_{\triangs}^{-1}y)$ we derive the claimed expression \begin{align*} \quasis_0(y,f(y))&=\frac{5}{4}-\frac{3}{2^{5/2}}\br{1-\rho_\triangs^{-1}y}^{1/2}+O\br{1-\rho_\triangs^{-1}y}. \end{align*} Given $n\in\N_0$, let us write $R^{(n)}(y,u) = \derivn{u}{n}R(y,u)$. By the choice of $f(y)$ we know that $R^{(0)}(y,f(y))=R^{(1)}(y,f(y))=0$. As $R(y,u)$ is a polynomial of degree four in $u$, we have $R^{(n)}(y,u)=0$ for all $n\ge5$. For $n\in\{2,3,4\}$, we obtain the dominant term of $R^{(n)}(y,f(y))$ by first differentiating $R(y,u)$ with respect to $u$ and then substituting $u=f(y)$, \eqref{triangulations}, \eqref{asyy}, and $y = \rho_{\triangs}-\rho_{\triangs}(1-\rho_{\triangs}^{-1}y)$. This yields \begin{align*} R^{(2)}(y,f(y))&=\frac{27}{2^{7/2}}\br{1-\rho_\triangs^{-1}y}^{1/2}+O\br{1-\rho_\triangs^{-1}y},\\ R^{(3)}(y,f(y))&=-\frac{675}{2^{16/3}}+O\br{\br{1-\rho_\triangs^{-1}y}^{1/2}},\\ R^{(4)}(y,f(y))&=-\frac{10125}{2^{23/3}}+O\br{\br{1-\rho_\triangs^{-1}y}^{1/2}}. \end{align*} We define $Q^{(n)}(y,u)$ and $P_0^{(n)}(y,u)$ analogously to $R^{(n)}(y,u)$. From the facts that $Q(y,f(y))=0$ and $\derivn{u}{n}\br{Q^2(y,u)}= R^{(n)}(y,u)$ we deduce that \begin{align}\label{eq:qr} \begin{split} 2nQ^{(1)}(y,f(y))Q^{(n-1)}(y,f(y)) =& \,R^{(n)}(y,f(y))\\ &- \sum_{k=2}^{n-2}\binom{n}{k}Q^{(k)}(y,f(y))Q^{(n-k)}(y,f(y)) \end{split} \end{align} for every $n\in\N$. For $n=2$, this implies that \begin{equation*} Q^{(1)}(y,f(y)) = \ol{c}(1-\rho_{\triangs}^{-1}y)^{1/4} + O\br{(1-\rho_{\triangs}^{-1}y)^{3/4}}, \end{equation*} where $\ol{c} = \pm\frac{3^{3/2}}{2^{11/4}}$. By differentiating $Q(y,u)=2yu^3\quasis_0(y,u)+q(y,u)$ with respect to $u$, we deduce that \begin{equation*} \quasis_0^{(1)}(y,f(y)) = \frac{75}{2^{13/3}}+\ol{c}\frac{125}{2^{59/12}3^{3/4}}\br{1-\rho_\triangs^{-1}y}^{1/4} +O\br{\br{1-\rho_\triangs^{-1}y}^{1/2}}. \end{equation*} Since $\quasis_0^{(1)}(y,u)$ is a generating function of a combinatorial class, all of its coefficients $[y^ku^l]\quasis_0^{(1)}(y,u)$ are nonnegative. As $f(y)$ has only nonnegative coefficients as well, all coefficients of $\quasis_0^{(1)}(y,u)\vert_{u=f(y)}$ are nonnegative, implying that $\ol{c} = -\frac{3^{3/2}}{2^{11/4}}$. For $n=3$, we deduce from \eqref{eq:qr} that \begin{equation*} Q^{(2)}(y,f(y)) = -\frac{675}{6\ol{c}2^{16/3}}(1-\rho_{\triangs}^{-1}y)^{-1/4} + O\br{(1-\rho_{\triangs}^{-1}y)^{1/4}}. \end{equation*} For $n\ge 4$, the term $R^{(n)}(y,f(y))$ is constant, while the sum on the right-hand side is nonempty. Since the sum only involves terms $Q^{(j)}(y,f(y))$ with $2\le j\le n-2$, we deduce by induction that \begin{equation} Q^{(n)}(y,f(y))=\ol{c}(n)\br{1-\rho_\triangs^{-1}y}^{-n/2+3/4}+O\br{\br{1-\rho_\triangs^{-1}y}^{-n/2+5/4}},\label{an} \end{equation} where $\ol{c}(n)$ is a constant depending only on $n$ and $\ol{c}(n)>0$ for $n\ge 2$. The claimed expressions of $\quasis_0^{(n)}(y,f(y))$ are now obtained by differentiating \[Q(y,u)=2y^2u^3\quasis_0(y,u)+q(y,u)\] $n$ times and by \eqref{triangulations}, \eqref{asyy}, \eqref{an}, and induction. As all generating functions in this proof are given by a system of algebraic equations, they are $\Delta$-analytic. \end{proof} \subsection{Recurrence for higher genus} Our next aim is to derive a recursion formula for $\quasis_g(y,u,z_I)$ and $\hat{\quasis}_g(y,u,z_I)$. Using the planar case in \Cref{inductionbase} as the base case, inductively applying the recursion formula allows us to derive similar statements as \Cref{inductionbase} for all $g$ and $I$. In order to derive the recursion formula, we will perform different surgeries on the surface depending on the placement of the root. We distinguish four cases. \renewcommand{\theenumi}{(\Alph{enumi})} \begin{enumerate} \item\label{rootedge:bridge} The root edge $e_r$ is only incident with the root face $f_r$ and is a bridge; \item\label{rootedge:nobridge} $e_r$ is only incident with $f_r$ and is not a bridge; \item\label{rootedge:marked} $e_r$ is incident with $f_r$ and one marked face; and \item\label{rootedge:unmarked} $e_r$ is incident with $f_r$ and one unmarked face. \end{enumerate} \renewcommand{\theenumi}{(\roman{enumi})} The recursion formula is then of the form \begin{equation} \quasis_g(y,u,z_I)=A_g(y,u,z_I)+B_g(y,u,z_I)+C_g(y,u,z_I)+D_g(y,u,z_I),\label{recursion-general} \end{equation} where $A_g(y,u,z_I)$, $B_g(y,u,z_I)$, $C_g(y,u,z_I)$, and $D_g(y,u,z_I)$ are the generating functions of the sub-classes $\class{A}_{g,I}$, $\class{B}_{g,I}$, $\class{C}_{g,I}$, and $\class{D}_{g,I}$ of $\class{\quasis}_{g,I}$ corresponding to the four cases \ref{rootedge:bridge}, \ref{rootedge:nobridge}, \ref{rootedge:marked}, and \ref{rootedge:unmarked} respectively. Each of the generating functions can be further decomposed as \begin{equation}\label{recursion:decompositions} \begin{split} A_g(y,u,z_I) &= a(y,u)\quasis_g(y,u,z_I)+\main_A(g;y,u,z_I)-\error_A(g;y,u,z_I),\\ B_g(y,u,z_I) &= b(y,u)\quasis_g(y,u,z_I)+\main_B(g;y,u,z_I)-\error_B(g;y,u,z_I),\\ C_g(y,u,z_I) &= c(y,u)\quasis_g(y,u,z_I)+\main_C(g;y,u,z_I)-\error_C(g;y,u,z_I),\\ D_g(y,u,z_I) &= d(y,u)\quasis_g(y,u,z_I)+\main_D(g;y,u,z_I)-\error_D(g;y,u,z_I), \end{split} \end{equation} where $a(y,u)$, $b(y,u)$, $c(y,u)$, and $d(y,u)$ are functions only involving the generating functions $P_0$ and $S_0$ of the planar case, while the other functions involve terms of the type $\quasis_{g'}(y,u,z_{I'})$ for $g'=triangle 45,x=1.0cm,y=1.0cm] \draw [color=black] (3.7,3.43) arc (70:123.5:2cm and 1cm); \draw [color=black] (1.03,2.65) arc (170:360:2cm and 1cm); \draw [color=red, dash pattern=on 1pt off 1pt] (1.9,3.33) arc (123.5:170:2cm and 1cm); \draw [color=red, very thick] (1.9,3.33) to[out=270,in=0] (1.03,2.65); \draw [color=red, dash pattern=on 1pt off 1pt] (5,2.5) arc (0:70:2cm and 1cm); \draw [color=red, very thick] (5,2.5) to[out=180,in=270] (3.7,3.43); \draw (1.9,3.7) node {$v_r'$}; \draw (3.7,3.7) node {$v'$}; \draw [color=red](1.8,2.6) node {$e_r'$}; \draw [color=red](3.9,2.6) node {$e'$}; \draw [color=black] (11,2.5) arc (0:360:2cm and 1cm); \draw [color=red,dash pattern= on 2pt off 2pt](7.03,2.65) to[out=310,in=260](8,2.5) to[out=80,in=20] (7.03,2.65); \draw [color=red,dash pattern= on 2pt off 2pt](9.7,3.43) to[out=230,in=170](9.6,2.6) to[out=350,in=300] (9.7,3.43); \draw (6.7,2.7) node {$v_r'$}; \draw (9.7,3.7) node {$v_2'$}; \begin{scriptsize} \draw [fill=black] (5,2.5) circle (1.5pt); \draw [fill=black] (3.7,3.43) circle (1.5pt); \draw [fill=black] (1.9,3.33) circle (1.5pt); \draw [fill=black] (1.03,2.65) circle (1.5pt); \draw [fill=black] (7.03,2.65) circle (1.5pt); \draw [fill=black] (9.7,3.43) circle (1.5pt); \end{scriptsize} \end{tikzpicture} \caption{Deriving an upper bound for $\error_B$.} \label{fig:caseb} \end{figure} In order to identify the corner $(v'_2,e'_2,e_2)$, we mark an arbitrary corner of the root face, which is again overcounting. Since we have to add one edge to $\tilde T$ and increase the valency of the root face by two to reconstruct $\tilde S$, we have an additional factor of $yu^2$, resulting in the claimed upper bound for $\error_B$. \end{proof} Similar arguments also show the corresponding result for $\hat{B}_g$. \begin{lem}\label{caseb2} The functions $\hat{b}(y,u,z_I)$, $\hat{\main}_B(g;y,u,z_I)$, and $\hat{\error}_B(g;y,u,z_I)$ are given by \begin{align*} \hat{b}(y,u,z_I)&=0,\\ \hat{\main}_B(g;y,u,z_I)&=yu^2\opa{{z_{i_0}}}\br{\hat{\quasis}_{g-1}(y,u,z_{I\cup\{i_0\}})}\big\vert_{z_{i_0}=u},\\ \hat{\error}_B(g;y,u,z_I)&=0. \end{align*} \end{lem} The only difference to the proof of \Cref{caseb} is that we do not need to compensate for overcounting in $\hat{\error}_B$, as all loops and double edges occurring in the proof are non-separating and thus allowed. In Case~\ref{rootedge:marked}, the root edge is not a bridge. Therefore, we will not be able to find a circle $C$ like in the previous two cases. On the other hand, deleting the root edge does not produce any faces that are not disks. Our construction in this case will thus start without cutting the surface. \begin{lem}\label{casec} The functions $c(y,u,z_I)$, $\main_C(g;y,u,z_I)$, and $\error_C(g;y,u,z_I)$ in \eqref{recursion:decompositions} are given by \begin{align*} c(y,u,z_I)&=0,\\ \main_C(g;y,u,z_I)&=y\sum_{i\in I}\sum_{T\in\class{\quasis}_g(I\setminus\{i\})}y^{|E(T)|} \prod_{j\neq i}z_j^{\beta_j(T)}\sum_{k=1}^{\beta(T)+1}u^kz_i^{\beta(T)+2-k},\\ 0 \preceq \error_C(g;y,u,z_I)&\preceq \,\sum_{i\in I}\bigg(\br{1+yu z_i}\opa{{z_i}}\br{\quasis_{g-1}(y,u,z_I)}\nonumber\\ &+\br{1+yu z_i}\sum_{t=0}^{g}\sum_{J\subseteq I\setminus\{i\}} \quasis_t(y,u,z_J)\quasis_{g-t}(y,z_i,z_{I\setminus (J\cup\{i\})})\bigg), \end{align*} where $\beta(T)$ and $\beta_j(T)$ denote the valencies of the root face of $T$ and of the face with index $j$ in $T$, respectively. \end{lem} Note that the sum in $\main_C$ is over all $i\in I$ and all $I\setminus\{i\}$-quasi-triangulations. As such, $\main_C$ can be written as \[ M_C = y \sum_{i \in I} \frac{u^2z_i P_g(y,u,z_{I\setminus \{ i \} }) - u z_i^2 P_g(y,z_i,z_{I\setminus \{ i \} })}{u-z_i}. \] However, similarly to \Cref{inductionbase}, we shall replace $u$ and $z_i$ by $f(y)$ in order to derive the desired asymptotic formulas, which would result in a division by $0$. For that reason we will use $\main_C$ as stated in \Cref{casec}. We will derive a more convenient formulation in \Cref{maincderiv}. \begin{proof}[Proof of \Cref{casec}] Let $S$ be an $I$-quasi-triangulation in $\class{C}_{g,I}$ with respect to $h\colon I\to F(S)$. We delete the root edge $e_r$, thus obtaining a map $T$ on $\torus{g}$. The root of $T$ is defined as follows. Let $e_r^-$ and $e_r^+$ be the predecessor and successor of $e_r$ at $v_r$, respectively; then $(v_r,e_r^-,e_r^+)$ is the root of $T$. By \ref{rootedge:marked}, $e_r$ was incident with a marked face $h(i)$. The root face of $T$ is $f'_r := f_r \cup e_r \cup h(i)$ and $T$ is an $(I\setminus\{i\})$-quasi-triangulation with respect to $h\vert_{I\setminus\{i\}}$. Let $c$ be a corner of $f'_r$ and let $\tilde S$ be obtained from $T$ by adding an edge $e_{\text{new}}$ from $(v_r,e_r^-,e_r^+)$ to $c$ and let the root of $\tilde S$ be \begin{itemize} \item $(v_r,e_{\text{new}},e_r^+)$ if $c\not=(v_r,e_r^-,e_r^+)$ and \item either $(v_r,e_{\text{new}},e_r^+)$ or $(v_r,e_{\text{new}},e_{\text{new}})$ otherwise. \end{itemize} These cases are illustrated in \Cref{fig:casec}. Adding $e_{\text{new}}$ divides $f'_r$ into two faces. One of these faces is the root face of $\tilde S$; we mark the other face with the index $i$ and denote the corresponding function $I\to F(\tilde S)$ by $\tilde h$. Clearly, there is a unique choice of $c\not=(v_r,e_r^-,e_r^+)$ such that $\tilde S = S$. If $c$ is a corner at $v_r$ (in particular if $c=(v_r,e_r^-,e_r^+)$), then $e_{\text{new}}$ will be a loop. If $c$ is a corner at a vertex adjacent to $v_r$, then $e_{\text{new}}$ will be part of a double edge. In either case, $\tilde S$ will not be simple and thus not an $I$-quasi triangulation. Although the case $c=(v_r,e_r^-,e_r^+)$ is clearly one of the cases when $\tilde S$ is not simple, it is slightly easier to derive the formulas including this case. \begin{figure}[htbp] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \draw [color=black] (1.13,2.16) arc (200:483.5:2cm and 1cm); \draw [color=red] (1.9,3.33) arc (123.5:200:2cm and 1cm); \draw [color=red, dash pattern= on 2pt off 2pt] (3.7,1.57) to[out=120,in=0] (1.03,2.65); \draw (0.75,2.75) node {$v_r$}; \draw [color=red](0.8,2.25) node {$e_r^-$}; \draw [color=red](1.4,3.4) node {$e_r^+$}; \draw [color=red](3,2.5) node {$e_{\text{new}}$}; \draw (2,2.15) node {$\tilde h(i)$}; \draw (3.8,2.6) node {$f_r$}; \draw (3.7,1.57) node[anchor=260] {$c$}; \draw [color=black] (7.13,2.16) arc (200:483.5:2cm and 1cm); \draw [color=red] (7.9,3.33) arc (123.5:200:2cm and 1cm); \draw [color=red,dash pattern= on 2pt off 2pt](7.03,2.65) to[out=300,in=270](9,2.5) to[out=80,in=30] (7.03,2.65); \draw (6.75,2.75) node {$v_r$}; \draw [color=red](6.8,2.25) node {$e_r^-$}; \draw [color=red](7.4,3.4) node {$e_r^+$}; \draw [color=red](9.1,2.5) node[anchor=east] {$e_{\text{new}}$}; \begin{scriptsize} \draw [fill=black] (1.13,2.16) circle (1.5pt); \draw [fill=black] (3.7,1.57) circle (1.5pt); \draw [fill=black] (1.03,2.65) circle (1.5pt); \draw [fill=black] (1.9,3.33) circle (1.5pt); \draw [fill=black] (7.9,3.33) circle (1.5pt); \draw [fill=black] (7.13,2.16) circle (1.5pt); \draw [fill=black] (7.03,2.65) circle (1.5pt); \end{scriptsize} \end{tikzpicture} \caption{Adding the edge $e_{\text{new}}$ from $(v_r,e_r^-,e_r^+)$ to $c$ to obtain $\tilde S$. If $c=(v_r,e_r^-,e_r^+)$, then each of the two faces can either be the root face or $\tilde h(i)$.} \label{fig:casec} \end{figure} As $f'_r$ has valency $\beta(T)$, there are $\beta(T)+1$ choices for $\tilde S$. The valency of the root face of $\tilde S$ is one if $c=(v_r,e_r^-,e_r^+)$ and the root face is $(v_r,e_{\text{new}},e_{\text{new}})$. If $c=(v_r,e_r^-,e_r^+)$ and the root face is $(v_r,e_{\text{new}},e_r^+)$, the valency is $\beta(T)+1$. Depending on which corner is chosen as $c$, the valency of the root face can take any value $k$ between $1$ and $\beta(T)+1$; the face $\tilde h(i)$ then has valency $\beta(T)+2-k$. The generating function of maps that can occur as $\tilde S$ from this particular $(I\setminus\{i\})$-quasi-triangulation $T$ is thus given by \[y^{|E(T)+1|}\left(\prod_{j\in I\setminus\{i\}}z_j^{\beta_j(T)}\right)\sum_{k=1}^{\beta(T)+1}u^kz_i^{\beta(T)+2-k}.\] This holds as the number of edges is increased by one and the valencies of all other marked faces do not change. After summing over all possible marked faces and all possible $T$, we obtain $\main_C$. As already mentioned, we overcount whenever the chosen corner $c$ is at $v_r$ or at a vertex adjacent to $v_r$, making $e_{\text{new}}$ a loop or part of a double edge, respectively. Suppose first that $e_{\text{new}}$ is part of a double edge. We zip the double edge. If it does not separate the surface, we have an upper bound $\opa{{z_i}}(\quasis_{g-1}(y,u,z_I))$ analogous to \Cref{caseb}. Indeed, the only difference to the corresponding case in \Cref{caseb} is that we mark a corner of (the face corresponding to) $\tilde h(i)$ instead of a corner of the root face, because $e_{\text{new}}$ was incident with both the root face and $\tilde h(i)$. If the double edge separates the surface, we obtain two maps $T_1$ on $\torus{t}$ for $0\le t\le g$ and $T_2$ on $\torus{g-t}$. One of the two maps, without loss of generality $T_2$, contains (the face corresponding to) $\tilde h(i)$. As $T_2$ is rooted at a corner of that face and the root face is never marked, the number of marks decreases by one. Thus, $T_1$ is a $J$-quasi-triangulation on $\torus{t}$ and $T_2$ is a $(I\setminus(J\cup\{i\}))$-quasi-triangulation on $\torus{g-t}$, where $J\subseteq I\setminus\{i\}$. Going back, all corners of the root face of $T_2$ become corners of the face with index $i$, meaning that we have to replace $u$ by $z_i$ in $\quasis_{g-t}(x,z_i,z_{I\setminus (J\cup\{i\})})$. This gives us an upper bound of \begin{equation*} \sum_{t=0}^{g}\sum_{J\subseteq I\setminus\{i\}} \quasis_t(x,u,J)\quasis_{g-t}(x,z_i,z_{I\setminus (J\cup\{i\})}). \end{equation*} If $e_{\text{new}}$ is a loop, then we proceed the same way as in \Cref{caseb}: we cut along $e_{\text{new}}$, close the two resulting holes by inserting disks, and delete the two copies of $e_{\text{new}}$. Like in \Cref{caseb}, the reverse construction yields the same bounds as in the case of $e_{\text{new}}$ being part of a double edge; the additional factor $yuz_i$ is due to the fact that we add one edge and increase the valencies of the root face and of $\tilde h(i)$ by one. \end{proof} Similar to \Cref{caseb,caseb2}, the only difference when using triangulations without separating loops or separating double edges instead of simple triangulations is in the calculation of $\hat{\error}_C$. The corresponding results are obtained by only keeping the terms in which separating loops or separating double edges are involved. \begin{lem}\label{casec2} The functions $\hat{c}(y,u,z_I)$, $\hat{\main}_C(g;y,u,z_I)$, and $\hat{\error}_C(g;y,u,z_I)$ are given by \begin{align*} \hat{c}(y,u,z_I)&=0,\\ \hat{\main}_C(g;y,u,z_I)&=y\sum_{i\in I}\sum_{T\in\hat{\class{\quasis}}_g(I\setminus\{i\})}y^{|E(T)|} \prod_{j\neq i}z_j^{\beta_j(T)}\sum_{k=1}^{\beta(T)+1}u^kz_i^{\beta(T)+2-k},\\ 0 \preceq \hat{\error}_C(g;y,u,z_I)&\preceq \,\sum_{i\in I} 2\br{1+yu z_i}\sum_{t=0}^g \sum_{J\subseteq I\setminus\{i\}} \hat{\quasis}_t(y,u,z_J)\hat{\quasis}_{g-t}(y,z_i,z_{I\setminus (J\cup\{i\})}), \end{align*} where $\beta(T)$ and $\beta_j(T)$ denote the valencies of the root face of $T$ and of the face with index $j$ in $T$, respectively. \end{lem} The difference between \Cref{casec} and \Cref{casec2} is that we do not need to compensate for the case where non-separating loops and double edges appear, since they are allowed in $\hat{\class{\quasis}}_{g,I}$. The construction in Case~\ref{rootedge:unmarked} is similar to Case~\ref{rootedge:marked}. The fact that the second face incident to $e_r$ is not marked makes the analysis easier. \begin{lem}\label{cased} The functions $d(y,u,z_I)$, $\main_D(g;y,u,z_I)$, and $\error_D(g;y,u,z_I)$ in \eqref{recursion:decompositions} are given by \begin{align*} d(y,u,z_I)&=yu^{-1}-y^2u-\triangs_0(y),\\ \main_D(g;y,u,z_I)&=-\triangs_g(y,z_I)\quasis_0(y,u),\\ 0 \preceq \error_D(g;y,u,z_I)&\preceq 3\quasis_{g-1}(y,u,z_{I\cup\{i_0\}})\vert_{z_{i_0}=u}+\sum_{t,J} \triangs_t(y,J)\quasis_{g-t}(y,u,z_{I\setminus J}), \end{align*} where the sum is taken over all $0 \leq t \leq g$ and $J\subseteq I$ with $(t,J)\neq(0,\emptyset)$ and $(t,J)\neq(g,I)$. \end{lem} \begin{proof} Let $S$ be an $I$-quasi-triangulation in $\class{D}_{g,I}$. We delete $e_r$ and choose the root of the resulting map $T$ to be $c'_r:=(v_r,e_r^-,e_r^+)$ like in \Cref{casec}. As the second face $f$ incident with $e_r$ is not marked and $S$ is an $I$-quasi-triangulation, $f$ is bounded by a triangle. Thus, $T$ is also an $I$-quasi-triangulation and the valency of its root face $f'_r$ is larger by one than the valency of $f_r$. For the reverse construction, consider the ordering of the corners of $f'_r$ in clockwise direction along its boundary and let $c$ be the corner after the next, starting from $c'_r$. We add an edge $e_{\text{new}}$ from $c'_r$ to $c$ and let $(v_r,e_{\text{new}},e_r^+)$ be the root of the resulting $I$-quasi-triangulation $\tilde S$. If $T$ was obtained from $S$ by deleting $e_r$, then $\tilde S=S$. However, if $T$ is an \emph{arbitrary} $I$-quasi-triangulation on $\torus{g}$, then $e_{\text{new}}$ might be a loop or part of a double edge. Thus, \begin{equation}\label{eq:nomark:upper} yu^{-1}\quasis_g(y,u,z_I) \end{equation} is only an upper bound for $D_g(y,u,z_I)$. Again, we have to subtract the cases when $\tilde S$ is not simple. The case when $e_{\text{new}}$ is a loop yields a term of \begin{equation}\label{eq:nomark:loop} -y^2u\quasis_g(x,u,z_I) \end{equation} analogously to \Cref{prop:baseplanar}. When $e_{\text{new}}$ is part of a double edge, we need to distinguish whether this double edge separates the surface. If it does separate, we obtain \begin{equation}\label{eq:nomark:separate} -\sum_{t=0}^{g}\sum_{J\subseteq I}\triangs_t(y,J)\quasis_{g-t}(y,u,z_{I\setminus J}) \end{equation} by zipping the double edge, similar to \Cref{casea}. The only differences are that the number of edges and the valencies of the faces do not change and that one of the two components is a $J$-triangulation, since its root face is $f$ and thus has valency three. Finally, if the double edge does not separate, then after zipping it we have to mark $f$ with a new index $i_0$ like in \Cref{caseb}. However, since the valency of $f$ is three, we only have three possible ways to reverse the construction. As the number of edges and all valencies remain unchanged, we have a summand \begin{equation}\label{eq:nomark:nonseparate} -3\quasis_{g-1}(y,u,z_{I\cup\{i_0\}})\vert_{z_{i_0}=u}\,. \end{equation} Note that \eqref{eq:nomark:nonseparate} is overcounting as the reverse construction can lead to additional loops or double edges. Combining \eqref{eq:nomark:upper}, \eqref{eq:nomark:loop}, and the term from \eqref{eq:nomark:separate} with $(t,J) = (0,\emptyset)$, we deduce the claimed expression for $d(y,u,z_I)$. The term from \eqref{eq:nomark:separate} with $(t,J) = (g,I)$ results in $\main_D(g;y,u,z_I)$; the remaining terms form the upper bound for $\error_D(g;y,u,z_I)$. \end{proof} Throughout the proof of \Cref{cased}, we do not encounter loops or multiple edges. Thus, the corresponding result for $\hat{D}$ follows immediately. \begin{lem}\label{cased2} The functions $\hat{d}(y,u,z_I)$, $\hat{\main}_D(g;y,u,z_I)$, and $\hat{\error}_D(g;y,u,z_I)$ are given by \begin{align*} \hat{d}(y,u,z_I)&=yu^{-1}-y^2u-\triangs_0(y),\\ \hat{\main}_D(g;y,u,z_I)&=-\hat{\triangs}_g(y,z_I)\hat{\quasis}_0(y,u),\\ 0 \preceq \hat\error_D(g;y,u,z_I)&\preceq 3\hat\quasis_{g-1}(y,u,z_{I\cup\{i_0\}})\vert_{z_{i_0}=u}+\sum_{t,J} \hat\triangs_t(y,J)\hat\quasis_{g-t}(y,u,z_{I\setminus J}), \end{align*} where the sum is taken over all $0 \leq t \leq g$ and $J\subseteq I$ with $(t,J)\neq(0,\emptyset)$ and $(t,J)\neq(g,I)$. \end{lem} \subsection{Asymptotics} We now compute the asymptotics of all generating functions involved. Among the generating functions of all cases, the only one with a different structure than the others is $\main_C$ which cannot be easily expressed in terms of $\quasis_{g'}(y,u,z_{I'})$ and $\triangs_{g'}(y,I')$ with some genus $g'$ and set $I'$. From $\main_B$ and $\error_B$ we observe that we need to calculate derivatives with respect to $u$ and $z_{i_0}$ and that we want to set $z_{i_0}=u$ in the end. We will be interested in the dominant term of $\quasis_g(y,u,z_I)$ when we set $u=f(y)$ and $z_i=f(y)$ for all $i\in I$; we will abbreviate this by $u=z_I=f(y)$. Observe that setting $u=z_I=f(y)$ does not have any influence on the functions $\triangs_g(y)$, as they only depend on the variable $y$. The following proposition enables us to express arbitrary derivatives of $\main_C$ (and $\hat{\main}_C$) at $u=z_I=f(y)$ in terms of derivatives of $\quasis_g$ (or $\hat{\quasis}_g$). \begin{prop}\label{maincderiv} Let $|y|<\rho_{\triangs}$, $n\in\N_0$, and $\alpha_i\in\N_0$ for all $i\in I$. Write $|\alpha_I|$ for $\sum \alpha_i$. Then \begin{align}\label{eq:mainc} &\frac{\partial^{n+|\alpha_I|}}{\partial u^n\prod_{i\in I}\partial z_i^{\alpha_i}} \main_C(g;y,u,z_I)\Bigg\vert_{u=z_I=f(y)}\\ &=y\br{\sum_{i\in I}\frac{n!\alpha_i!}{(n+\alpha_i+1)!}\frac{\partial^{n+1+|\alpha_I|}}{\partial u^{n+1+\alpha_i} \prod_{j\in I\setminus\{i\}}\partial z_j^{\alpha_j}}\br{u^3\quasis_g(y,u,z_{I\setminus\{i\}})}}\Bigg\vert_{u=z_I=f(y)} \,.\nonumber \end{align} \end{prop} \begin{proof} The generating function $yu^3\quasis_g(y,u,z_{I\setminus\{i\}})$ is given by \begin{equation*} yu^3\quasis_g(y,u,z_{I\setminus\{i\}})=y\sum_{T\in\class{\quasis}_g(I\setminus\{i\})} y^{|E(T)|}u^{\beta(T)+3}\prod_{j\in I\setminus\{i\}}z_j^{\beta_j(T)}. \end{equation*} By comparing this term with the summand in \begin{equation*} \main_C(g;y,u,z_I)=y\sum_{i\in I}\sum_{T\in\class{\quasis}_g(I\setminus\{i\})}y^{|E(T)|} \prod_{j\neq i}z_j^{\beta_j(T)}\sum_{k=1}^{\beta(T)+1}u^kz_i^{\beta(T)+2-k} \end{equation*} for a fixed index $i\in I$, one sees that the difference between them is that the factor $u^{\beta(T)+3}$ is replaced by $\sum_{k=1}^{\beta(T)+1}u^kz_i^{\beta(T)+2-k}$. Taking the derivatives with respect to $u$ and $z_i$ the given number of times and comparing the coefficients yields factors \begin{align*} \frac{(\beta(T)+3)!}{(\beta(T)+2-n-\alpha_i)!}&u^{\beta(T)+2-n-\alpha_i} &\text{and}&\\ \sum_{k=n}^{\beta(T)+2-\alpha_i}\frac{k!(\beta(T)+2-k)!}{(k-n)!(\beta(T)+2-k-\alpha_i)!}&u^{\beta(T)+2-n-\alpha_i}, && \end{align*} respectively, when $n+\alpha_i+1 \le \beta(T)+3$ and factors $0$ otherwise. The quotient of these two coefficients equals $\frac{n!\alpha_i!}{(n+\alpha_i+1)!}$ by a binomial identity. Summing over $i\in I$ finishes the proof. \end{proof} \begin{remark} With the same proof, the analogous result for $\hat{\main}_C$ and $\hat{\quasis}_g$ holds as well. \end{remark} The only other term where differentiating is not straight forward is $\main_B$. By using the chain rule $n$ times we obtain \begin{align} \frac{\partial^{n+|\alpha_I|}}{\partial u^n\prod_{i\in I}\partial z_i^{\alpha_i}}&\main_B(g;y,u,z_I)\label{mainb}\\ =&\frac{\partial^{n+|\alpha_I|}}{\partial u^n\prod_{i\in I}\partial z_i^{\alpha_i}}\br{yu^2\br{z_{i_0}\deriv{{z_{i_0}}}\quasis_{g-1}\br{y,u,z_{I\cup\{i_0\}}}}\bigg\vert_{z_{i_0}=u}}\nonumber\\ =&y\sum_{k=0}^n\binom{n}{k}\br{\frac{\partial^{n-k+|\alpha_I|}}{\partial u^{n-k}\prod_{i\in I}\partial z_i^{\alpha_i}}\derivn{z_{i_0}}{k+1}\br{u^3\quasis_{g-1}\br{y,u,z_{I\cup\{i_0\}}}}}\bigg\vert_{z_{i_0}=u}.\nonumber \end{align} Using \eqref{eq:mainc} and \eqref{mainb} we can now determine the dominant terms of the derivatives of $\triangs_g$ and $\quasis_g$ (and analogously the derivatives of $\hat{\triangs}_g$ and $\hat{\quasis}_g$). \begin{thm}\label{finalind} Let $\alpha_i\in\N_0$, $i\in I$, and $|\alpha_I|:=\sum\alpha_i$. If $(g,I)\neq (0,\emptyset)$, then \begin{equation}\label{rec-triang} \frac{\partial^{|\alpha_I}|}{\prod\partial z_i^{\alpha_i}}\triangs_g(y,z_{I})\bigg\vert_{z_I=f(y)}\cong a_0 + c_g\br{1-\rho_{\triangs}^{-1}y}^{e_1}+O\br{\br{1-\rho_{\triangs}^{-1}y}^{e_1+1/4}}, \end{equation} where $a_0$ and $c_g=c_g(\alpha_i,i\in I)$ are positive constants and \[e_1=-\frac{5g}{2}-\frac{5|I|}{4}-\frac{|\alpha_I|}{2}+\frac{3}{2}.\] $\left.\derivn{u}{n}P_0(y,u)\right\vert_{u=f(y)}$ is given as in \Cref{inductionbase}. If $(g,I,n)\neq (0,\emptyset,0)$, then \begin{equation}\label{rec-quasi} \frac{\partial^{n+|\alpha_I|}}{\partial u^n\prod\partial z_i^{\alpha_i}} \quasis_g(y,u,z_{I})\bigg\vert_{u=z_I=f(y)}\cong c \br{1-\rho_{\triangs}^{-1}y}^{e_2}+O\br{\br{1-\rho_{\triangs}^{-1}y}^{e_2+1/4}}, \end{equation} where $c=c(g,|I|,n,|\alpha_I|)$ is a positive constant and \[e_2=e_1-\frac{n}{2}-\frac{3}{4}.\] \end{thm} \begin{proof} We show this by induction on $(g,|I|,n)$ in lexicographic order. \Cref{inductionbase} shows that \eqref{rec-quasi} is true for $(g,I)=(0,\emptyset)$ and $n>0$. Note that $|\alpha_I|=0$ for $I=\emptyset$. Suppose now that \eqref{rec-quasi} is true for all $(g,|I|,n)< (g_0,|I_0|,0)$ and \eqref{rec-triang} is true for all $(g,|I|)<(g_0,|I_0|)$ with $(g,I)\not=(0,\emptyset)$. We first prove that \eqref{rec-triang} holds for $(g_0,|I_0|)$. By multiplying \eqref{recursion-general} by $u$ and applying \Cref{casea,caseb,casec,cased} we obtain \begin{equation*} u(1-a-d)\quasis_{g_0}(y,u,z_{I_0})=u(\main_A+\main_B+\main_C)-u\triangs_{g_0}(y,z_{I_0})\quasis_0(y,u)-u\error, \end{equation*} where $\error=\error_B+\error_C+\error_D$. The term \begin{equation*} u(1-a-d)=u-2yu^3\quasis_0(y,u)-u\triangs_0(y)-y+y^2u^2 \end{equation*} is equal to $-Q(y,u)$ in \eqref{quadrat} and thus \begin{equation}\label{recursionexplicit} -Q(y,u)\quasis_{g_0}(y,u,z_{I_0})=u(\main_A+\main_B+\main_C)-u\triangs_{g_0}(y,z_{I_0})\quasis_0(y,u)-u\error. \end{equation} Therefore, the left-hand side is zero when replacing $u$ by $f(y)$. As this factor is independent of $z_{I_0}$, this does also hold when differentiating the equation $\alpha_i$ times with respect to $z_i$. Thus we obtain \begin{align*} u\quasis_0(y,u)\frac{\partial^{|\alpha_{I_0}|}\triangs_{g_0}(y,z_{I_0})}{\prod\partial z_i^{\alpha_i}}\bigg\vert_{u=z_{I_0}=f(y)}&= u\frac{\partial^{|\alpha_{I_0}|}(\main_A+\main_B+\main_C-\error)}{\prod\partial z_i^{\alpha_i}}\bigg\vert_{u=z_{I_0}=f(y)}. \end{align*} By inspecting the formulas for $\main_A$ to $\error_D$ in \Cref{casea,caseb,casec,cased}, one sees that all occurring terms are lexicographically smaller than $(g_0,|I_0|,0)$ ,and the induction hypothesis can thus be used. Inspection of the exponents of $(1-\rho_{\triangs}^{-1}y)$ in all those terms shows the following. \begin{itemize} \item[$\main_A$:] The summands have the form \begin{equation*} \frac{\partial^{|\alpha_{I_0}|}}{\prod\partial z_i^{\alpha_i}}\br{\quasis_t\br{y,u,z_J}\quasis_{g_0-t}\br{y,u,z_{I_0\setminus J}}} \end{equation*} for $(t,J)\not=(0,\emptyset)$ and $(t,J)\not=(g_0,I_0)$. Thus, for $g_0+|I_0|\le 1$, we have $\main_A=0$. For all other values of $(g_0,|I_0|)$, each summand is of the form $c_A(1-\rho_{\triangs}^{-1}y)^{m_A}+O\br{(1-\rho_{\triangs}^{-1}y)^{m_A+1/4}}$ with \begin{align*} m_A&=-\frac{5t}{2}-\frac{5|J|}{4}-\frac{|\alpha_J|}{2}+\frac{3}{4}-\frac{5(g_0-t)}{2}-\frac{5|I_0\setminus J|}{4}-\frac{|\alpha_{I_0\setminus J}|}{2}+\frac{3}{4}=e_1 \end{align*} by induction. Furthermore, all coefficients are positive by induction. \item[$\main_B$:] We have $\main_B = yu^2\opa{{z_{i_0}}}\br{\quasis_{{g_0-1}}(y,u,z_{I\cup\{i_0\}})}\mid_{z_{i_0}=u}$. Thus, for $g_0=0$ we have $\main_B=0$ and otherwise $\main_B = c_B(1-\rho_{\triangs}^{-1}y)^{m_B}+O\br{(1-\rho_{\triangs}^{-1}y)^{m_B+1/4}}$ with \begin{align*} m_B&=-\frac{5(g_0-1)}{2}-\frac{5|I_0\cup\{i_0\}|}{4}-\frac{|\alpha_{I_0}|+1}{2}+\frac{3}{4}=e_1 \end{align*} by induction. Again, the coefficient is positive by induction. \item[$\main_C$:] We determine the expression for $\main_C$ by \Cref{maincderiv}. For $g_0=0$ and $|I_0|=1$ we have $\main_C \cong c_{C,1}(1-\rho_{\triangs}^{-1}y)^{1/4}+O\br{(1-\rho_{\triangs}^{-1}y)^{1/2}}$, which is of the desired order, since $e_1=1/4$ in this case. For all other $(g_0,I_0)$, induction yields that $\main_C = c_{C,2}(1-\rho_{\triangs}^{-1}y)^{m_C}+O\br{(1-\rho_{\triangs}^{-1}y)^{m_C+1/4}}$ with \begin{align*} m_C&=-\frac{5g_0}{2}-\frac{5(|I_0|-1)}{4}-\frac{|\alpha_{I_0}|}{2}-\frac{1}{2}+\frac{3}{4}=e_1\,. \end{align*} Like in the previous cases, the coefficient is positive by induction. \item[$\error_B$:] The function $\error_B$ is bounded from above by $\br{yu^2+1}\opa{u}\br{\quasis_{g_0-1}(y,u,z_{I_0})}$. For $g_0=0$, we thus have $\error_B=0$ and otherwise $\error_B = O\br{(1-\rho_{\triangs}^{-1}y)^{e_B}}$ with \begin{align*} e_B&=-\frac{5(g_0-1)}{2}-\frac{5|I_0|}{4}-\frac{|\alpha_{I_0}|}{2}-\frac{1}{2}+\frac{3}{4}\ge e_1+\frac14\,. \end{align*} \item[$\error_C$:] The first summand in the expression of $\error_C$ from \Cref{casec} is $0$ if $g_0=0$ and otherwise $O((1-\rho_{\triangs}^{-1}y)^{e_{C,1}})$ with \begin{align*} e_{C,1}&=-\frac{5(g_0-1)}{2}-\frac{5|I_0|}{4}-\frac{|\alpha_{I_0}|+1}{2}+\frac{3}{4}\ge e_1+\frac14\,. \end{align*} The second summand is $a_{\error}+O\br{(1-\rho_{\triangs}^{-1}y)^{1/2}}$ if $g_0=0$ and $|I_0|=1$. Suppose $(g_0,|I_0|)\not=(0,1)$. Then every term \[\br{1+yu z_i}\quasis_t(y,u,z_J)\quasis_{g-t}(y,z_i,z_{I\setminus (J\cup\{i\})})\] with $(t,J)\not=(0,\emptyset)$ and $(t,J)\not=(g_0,I_0\setminus\{i\})$ is $O((1-\rho_{\triangs}^{-1}y)^{e_{C,2}})$ with \begin{align*} e_{C,2}&=-\frac{5t}{2}-\frac{5|J|}{4}-\frac{|\alpha_J|}{2}+\frac{3}{4}-\frac{5(g_0-t)}{2}-\frac{5(|I_0\setminus J|-1)}{4}-\frac{|\alpha_{I_0\setminus J}|-\alpha_i}{2}+\frac{3}{4}\\ &\ge e_1+\frac14 \end{align*} by induction. The corresponding terms for $(t,J)=(0,\emptyset)$ and $(t,J)=(g_0,I_0\setminus\{i\})$ are $O\br{(1-\rho_{\triangs}^{-1}y)^{e_{C,3}}}$ with \begin{align*} e_{C,3}&=-\frac{5g_0}{2}-\frac{5(|I_0|-1)}{4}-\frac{|\alpha_{I_0}|-\alpha_i}{2}+\frac{3}{4}\ge e_1+\frac14\,. \end{align*} In total, we have $\error_C = O\br{(1-\rho_{\triangs}^{-1}y)^{e_1+1/4}}$. \item[$\error_D$:] The first summand in the expression of $\error_D$ from \Cref{cased} is $0$ if $g_0+|I_0|\le 1$ and otherwise each of its summands is $O\br{(1-\rho_{\triangs}^{-1}y)^{e_{D,1}}}$ with \begin{align*} e_{D,1}&=-\frac{5t}{2}-\frac{5|J|}{4}-\frac{|\alpha_J|}{2}+\frac{3}{2}-\frac{5(g_0-t)}{2}-\frac{5|I_0\setminus J|}{4}-\frac{|\alpha_{I_0\setminus J}|}{2}+\frac{3}{4}\\ &\ge e_1+\frac14 \end{align*} by induction. The second term is $0$ for $g_0=0$ and $O\br{(1-\rho_{\triangs}^{-1}y)^{e_{D,2}}}$ otherwise with \begin{align*} e_{D,2}&=-\frac{5(g_0-1)}{2}-\frac{5(|I_0|+1)}{4}-\frac{|\alpha_{I_0}|}{2}+\frac{3}{4}\ge e_1+\frac14\,. \end{align*} \end{itemize} Note that for $\hat{\quasis}_g$ the only difference is in the formulas of $\hat{\error}_B$ and $\hat{\error}_C$, both of which satisfy the same inequalities as $\error_B$ and $\error_C$ above. Thus the following conclusions also hold for $\hat{\quasis}_g$. Combining these results, we have proved \eqref{rec-triang}, where $a_0=a_{\main}-a_{\error}$ for $g_0=0$ and $|I_0|=1$. As this constant is the value of the generating function $\triangs_0(y,z_{I_0})\vert_{z_{I_0}=f(y)}$ at its singularity $\rho_{\triangs}$, $a_0$ is positive. For $|\alpha_{I_0}|>0$ or $(g_0,|I_0|)\not=(0,1)$, the exponent $e_1$ is negative and \eqref{rec-triang} is thus true with the same value for $a_0$. Finally, $c_g$ is positive, since it is the sum of positive numbers. To prove \eqref{rec-quasi}, recall that we assume that \eqref{rec-quasi} is true for $(g,|I|,n)<(g_0,|I_0|,0)$ and we have already shown that \eqref{rec-triang} is true for $(g,|I|)\le(g_0,|I_0|)$. Let $n_0\in\N_0$ and assume that \eqref{rec-quasi} is also true for $(g_0,|I_0|,n)$ with $n0$. Since $\deriv{u}Q(y,u)\vert_{u=f(y)} = \ol{c}(1-\rho_{\triangs}^{-1}y)^{1/4}+O\br{(1-\rho_{\triangs}^{-1}y)^{1/2}}$ with $\ol{c}<0$, \eqref{rec-quasi} follows. \end{proof} An analogous proof yields the corresponding result for $\hat{\class\triangs}_g$ and $\hat{\class\quasis}_g$, with identical constants $a_0,c_g,c,e_1,e_2$. By \Cref{inductionbase} and setting $I=\emptyset$ in \eqref{rec-triang} we deduce \Cref{simplerefined} and, from the corresponding result for $\hat{\triangs}_g$, also \Cref{essentialsimple}. \end{document}