\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.30}{25(1)}{2018}

\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{\bf 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}
\quad \quad Mihyun Kang\textsuperscript{\fnsymbol{footnote}}\thanks{Supported by Austrian Science Fund (FWF): P27290 and W1230 II}\\
Michael Mo{\ss}hammer\textsuperscript{\fnsymbol{footnote}}\quad \quad
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}{Feb 16, 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<R$ and $\theta\in(0,\pi/2)$,
\begin{equation*}
  \Delta(\rho,R,\theta) := \{ z\in\C \mid |z| < R \,\land\, |\arg(z-\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'<g$, because the surgery does not create loops or double edges.
Thus, disregarding markings, in the first case $M^{(1)} \in \class\triangs_{g_1}$ and $M^{(2)} \in \class\triangs_{g_2}$ with $g_1 + g_2 = g$ and $g_1, g_2 \geq 1$, and then in the second case $M^* \in \class\triangs_{g-1}$. 

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[line cap=round,line join=round,>=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'<g$, \eqref{eq:asys} yields 
\begin{align}
 \frac{1}{k!}\prod_{i=1}^k\one_{g_i}(v)\cong O\br{(1-\rho_{\one}^{-1}v)^{-5g/2+5/2+2}}\label{eq:b}
\end{align}
and thus 
\[G_g(v)\preceq c_g(1-\rho_{\one}^{-1}v)^{-5g/2+5/2}+O\br{(1-\rho_{\one}^{-1}v)^{-5g/2+11/4}}.\]

We derive a lower bound for $g\ge 1$ as follows. Let $\tilde{\class{G}}_g$ be the class of graphs in $\class{G}_g$ with one component of genus $g$ and all other components planar. Then
\begin{align*}
 \sum_{j=0}^{\infty}\frac{C_g(v)C_0^j(v)}{(j+1)!}\succeq \tilde{G}_g(v)\succeq \sum_{j=0}^{\infty}\frac{C_g(v)C_0^j(v)}{(j+1)!}-\sum_{j=0}^{\infty}\frac{(j+1)C_0^{j+1}(v)}{(j+1)!}.
\end{align*}
Indeed, if the component of genus $g$ is also planar, then the graph might be counted up to $j+1$ times (once for each 
component) on the left-hand side. Substituting the corresponding summands thus yields a lower bound of $\general_g(v)$. 
\begin{align}
	\vertex{\general}_g(v)\succeq \tilde{\general}_g(v)\succeq \sum_{j=0}^\infty\frac{1}{(j+1)!}\one_g(v)\one_0^j(v)-\sum_{j=1}^\infty\frac{j}{j!}\one_0^j(v).\label{lowerbd}
\end{align}
Applying \Cref{tt} to the upper and lower bounds and setting $\gamma_2=\rho_{\one}^{-1}$ completes the proof.\qed

\subsection{Proofs of Theorems \ref{main1}, \ref{main3}, and \ref{main4}}
\Cref{main1,main3} can be proven in a similar way as \Cref{main2}. We obtain $\rho_1=\gamma_1^{-1}$ as the square 
root of the smallest positive solution of
\[0=46656 - 279936 u - 7293760 u^2 - 513216 u^3 + 148716 u^4 - 17469 u^5 + 729 u^6\]
and $\rho_3=\gamma_3^{-1}$ as the square root of the smallest positive solution of 
\[0=46656 + 279936 u - 7293760 u^2 + 513216 u^3 + 148716 u^4 + 17469 u^5 + 729 u^6.\]

\Cref{main4} for the case of weighted multigraphs follows immediately from~\eqref{eq:a}, \eqref{eq:b}, and \Cref{tt}.
Indeed, \eqref{eq:a} and \Cref{tt} imply that the number of weighted multigraphs in $\class{\general}_g(n)$ that
have a unique non-planar component that is not embeddable on $\torus{g-1}$ is
\[\br{1+O\br{n^{-1/4}}}e_g n^{5g/2-5/2}\gamma_2^{2n}(2n)!\,.\]
On the other hand, \eqref{eq:b} and \Cref{tt} imply that the number of weighted multigraphs in $\class{\general}_g(n)$
that do not have such a component is
\[O\br{n^{5g/2-5/2-2}\gamma_2^{2n}(2n)!}.\]
Thus, \Cref{main4} follows. Observe that the probability $1-O(n^{-2})$ is not sharp. Indeed, the exponent in
\eqref{eq:b} could be improved to $-5g/2+5-\varepsilon$ for every $\varepsilon>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'<g$ or $I'\subsetneq I$. This will enable
us to use \eqref{recursion-general} to recursively determine the dominant terms of $\quasis_g(y,u,z_I)$. In this recursion,
the functions $\main_A$, $\main_B$, $\main_C$, and $\main_D$ will contribute to the dominant term; the functions
$\error_A$, $\error_B$, $\error_C$, and $\error_D$ turn out to be of smaller order.

The classes $\hat{\class{A}}_{g,I}$, $\hat{\class{B}}_{g,I}$, $\hat{\class{C}}_{g,I}$, and 
$\hat{\class{D}}_{g,I}$ together with the functions $\hat{A}_g(y,u,z_I)$, $\hat{a}(y,u)$, 
$\hat{\main}_A(g;y,u,z_I)$, and $\hat{\error}_A(g;y,u,z_I)$ (and similarly for $B$, $C$, and 
$D$) are defined analogously.

We start by determining the functions for Case~\ref{rootedge:bridge}. In this case, after deleting the root edge
we can split the map into two maps whose genera add up to $g$.

\begin{lem}\label{casea}
 The functions $a(y,u,z_I)$, $\main_A(g;y,u,z_I)$, and $\error_A(g;y,u,z_I)$ in \eqref{recursion:decompositions}
 are given by
 \begin{align*}
  a(y,u,z_I)&=2yu^2\quasis_0(y,u),\\
  \main_A(g;y,u,z_I)&=yu^2\sum_{t,J}\quasis_t\br{y,u,z_J}\quasis_{g-t}\br{y,u,z_{I\setminus J}},\\
  \error_A(g;y,u,z_I)&=0.
 \end{align*}
 The sum is over $t = 0,\dotsc,g$ and $J\subseteq I$ such that $(t,J)\neq(0,\emptyset)$ and 
 $(t,J)\neq(g,I)$.
\end{lem}
\begin{proof}
  Let $S$ be an $I$-quasi-triangulation in $\class{A}_{g,I}$, with respect to $h\colon I\to F(S)$, say.
  By \ref{rootedge:bridge}, 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. Since $e_r$ was a bridge, this
  surgery results in two components $S_1$ and $S_2$. We define the roots of $S_1$ and $S_2$ like in
  \Cref{prop:baseplanar}: let $v_1$ and $v_2$ be the end vertices of $e_r$ in $S_1$ and $S_2$ respectively.
  Without loss of generality 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 root of $S_1$ and $S_2$ respectively. Denote the root faces by $f_1$ and $f_2$ respectively. These are
  the faces of $S_1$ and $S_2$ into which the disks were inserted.

  Since every face in $F(S)\setminus\{f_r\}$ corresponds to a face in $F(S_1)\setminus\{f_1\}$ or in $F(S_2)\setminus\{f_2\}$,
  $h$ induces a function $\tilde h \colon I \to (F(S_1)\cup F(S_2))\setminus\{f_1,f_2\}$. If we write $J =
  \tilde h^{-1}(F(S_1))$, then $S_1$ is a $J$-quasi-triangulation on a surface of genus $t\le g$; consequently, $S_2$
  is an $(I\setminus J)$-quasi-triangulation on a surface of genus $g-t$. By deleting $e_r$, we decreased the number of corners
  of $f_r$ by two; the surgery then distributed the remaining corners of $f_r$ to $f_1$ and $f_2$. Therefore, the sum of valencies
  of $f_1$ and $f_2$ is smaller by two than the valency of $f_r$. On the other hand, we clearly have $|E(S_1)| + |E(S_2)| = |E(S)| - 1$.
  The reverse operation of the surgery is to delete an open disk from each of $f_1,f_2$, glue the surfaces along the boundaries
  of these disks, and add an edge from the root corner of $S_1$ to the root corner of $S_2$. As this operation is uniquely
  defined, we deduce that
 \[  A_g(y,u,z_I)=yu^2\sum_{t=0}^g\sum_{J\subseteq I}\quasis_t\br{y,u,z_J}\quasis_{g-t}\br{y,u,z_{i\setminus J}}.\]
  Extracting the terms for $(t,J)=(0,\emptyset)$ and $(t,J)=(g,I)$ finishes the proof.
\end{proof}

\begin{remark}
 Analogously to \Cref{casea}, we have
 \begin{align*}
  \hat{a}(y,u,z_I)&=2yu^2\hat{\quasis}_0(y,u),\\
  \hat{\main}_A(g;y,u,z_I)&=yu^2\sum_{t,J}\hat{\quasis}_t\br{y,u,z_J}\hat{\quasis}_{g-t}\br{y,u,z_{I\setminus J}},\\
  \hat{\error}_A(g;y,u,z_I)&=0,
 \end{align*}
 where the sum is over $t = 0,\dotsc,g$ and $J\subseteq I$ such that $(t,J)\neq(0,\emptyset)$ and 
 $(t,J)\neq(g,I)$.
\end{remark}
This follows by the same proof as for \Cref{casea}, because no loops or double edges occur in that construction.

For Case~\ref{rootedge:nobridge}, we will cut the surface along a circle contained in $f_r\cup e_r$ and close
the holes by inserting disks. However, because the surface will not be separated by this surgery, one needs to keep track 
of where to cut and glue to reverse the surgery. To this end we have to mark faces. Therefore, the index set $I$ will increase.

\begin{lem}\label{caseb}
 The functions $b(y,u,z_I)$, $\main_B(g;y,u,z_I)$, and $\error_B(g;y,u,z_I)$ in \eqref{recursion:decompositions}
 are given by
 \begin{align*}
  b(y,u,z_I)&=0,\\
  \main_B(g;y,u,z_I)&=yu^2\opa{{z_{i_0}}}\br{\quasis_{g-1}(y,u,z_{I\cup\{i_0\}})}\big\vert_{z_{i_0}=u},\\
  0 \preceq \error_B(g;y,u,z_I)&\preceq\br{1+yu^2}\opa{u}\br{\quasis_{g-1}(y,u,z_I)}.
 \end{align*}
\end{lem}

\begin{proof}
  Let $S$ be an $I$-quasi-triangulation in $\class{B}_{g,I}$, with respect to $h\colon I\to F(S)$.
  We use the analogous surgery as in \Cref{casea}, with the difference that $S$ is not separated by cutting along the
  circle $C$. Therefore we only obtain one map $T$. One of the end vertices of $e_r$ is the root vertex $v_r$ of
  $S$. Let $e_r^-$ and $e_r^+$ be the predecessor and successor of $e_r$
  in the cyclic order of edges of $S$ at $v_r$, respectively. Then we define the root of $T$ to be $(v_r,e_r^-,e_r^+)$.
  Denote the root face of $T$ by $f'_r$; this is one of the two faces into which we inserted disks to close the holes
  during our surgery. Denote the other such face by $f_2$. We mark $f_2$ by adding a new index $i_0$ to the index
  set $I$ and extend the function $h$ to $I\cup\{i_0\}$ by setting $h(i_0) := f_2$. Then $T$ is an
  $(I\cup\{i_0\})$-quasi-triangulation on $\torus{g-1}$.

  To reverse the surgery, we delete an open disk from each of $f'_r$, $f_2$, glue the surface along the boundaries
  of these disks, add a new edge $e_{\text{new}}$ from the root corner of $T$ to a corner $c_2$ of $f_2$, and let
  $(v_r,e_{\text{new}},e_r^+)$ be the new root corner.
  We thus have to mark a corner of $f_2$, which corresponds to applying the operator $\opa{{z_{i_0}}}$ to the
  generating function. After gluing, the corners of $f_2$ become corners of the new root face; we thus have to
  remove $i_0$ from the index set and replace $z_{i_0}$ by $u$ in the generating function. Like in the previous
  cases, adding $e_{\text{new}}$ increases the total number of edges by one and the valency of the root face by
  two, as $e_{\text{new}}$ lies only on the boundary of the new root face. This results in the term
  $yu^2\opa{{z_{i_0}}}\br{\quasis_{g-1}(y,u,z_{I\cup\{i_0\}})}\mid_{z_{i_0}=u}$.

  However, by this construction we have overcounted. If the vertex $v$ of the corner $c_2$ is adjacent to
  $v_r$, then $e_{\text{new}}$ will be part of a double edge; if $v=v_r$, $e_{\text{new}}$ will be a loop. We want
  to subtract all resulting maps $\tilde S$ for which $e_{\text{new}}$ is a loop or part of a double edge. Suppose first that
  $e_{\text{new}}$ is part of a double edge. Since $e_{\text{new}}$ lies only on the boundary of the root face of
  $\tilde S$, the double edge is not separating. Thus, zipping it results in an $I$-quasi-triangulation $\tilde T$
  on $\torus{g-1}$. One of the two zipped edges is the root edge $e'_r$ of $\tilde T$, denote the other zipped edge
  by $e'$. Both $e'_r$ and $e'$ lie on the boundary of the root face (see \Cref{fig:caseb}). Let $v'_r$ be the
  root vertex of $\tilde T$; then $v'_r$ is one of the two copies of $v_r$. If we denote the other copy by $v'$, then
  $v'$ is an end vertex of $e'$ and thus there is a corner $c'=(v',e'',e')$ of the root face of $\tilde T$. We can
  reconstruct $\tilde S$ from $\tilde T$ in the following way: cut along $e'_r$ and $e'$ and glue the surface along
  the boundaries of the resulting holes in the unique way that identifies $v'_r$ and $v'$. Identifying the corner
  $c'$ is bounded by marking an \emph{arbitrary} corner of the root face of $\tilde T$. This corresponds to applying
  the operator $\opa{u}$ to the generating function $\quasis_{g-1}(y,u,z_I)$. As zipping a double edge does neither change
  the number of edges nor the valencies of faces, $\opa{u}\br{\quasis_{g-1}(y,u,z_I)}$ is an upper bound in this case.

  Suppose now that $e_{\text{new}}$ is a loop and recall that $(v_r,e_{\text{new}},e_r^+)$ is the root corner of
  $\tilde S$. Since $e_{\text{new}}$ lies only on the boundary of the root face of $\tilde S$, there is a unique
  edge $e_2\not=e_r^+$ such that $(v_r,e_{\text{new}},e_2)$ is a corner of the root face. We cut along $e_{\text{new}}$,
  close the two resulting holes by inserting disks, and delete the two copies of $e_{\text{new}}$.
  Again, cutting does not separate the surface. Thus, we obtain a map $\tilde T$ on $\torus{g-1}$
  that does not have loops or double edges. Let $v'_r$ be the copy of $v_r$ in $\tilde T$ that is incident with
  $e_r^+$ and let $v'_2$ be the other copy. Then the root of $\tilde T$ is $(v'_r,e',e_r^+)$ for some edge $e'$.
  Furthermore, the root face of $\tilde T$ has a corner $(v'_2,e'_2,e_2)$. Now $\tilde S$ can be reconstructed from
  $\tilde T$ in the following way (see \Cref{fig:caseb}).
  \begin{enumerate}
  \item Add a loop at each of $(v'_r,e',e_r^+)$ and $(v'_2,e'_2,e_2)$;
  \item delete the resulting two faces of valency one;
  \item identify the two loops.
  \end{enumerate}
 
  \begin{figure}[htbp]
  \centering
   \begin{tikzpicture}[line cap=round,line join=round,>=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 $n<n_0$. Consider the derivative $\derivn{u}{n+1}$ of
\eqref{recursionexplicit} and set $u=f(y)$; as $Q(y,f(y))=0$, this yields
\begin{equation*}
  -\left.\sum_{k=0}^{n}\binom{n+1}{k}\derivn{u}{k}P_{g_0}(y,u,z_{I_0})\derivn{u}{n+1-k}Q(y,u)\right\vert_{u=z_{I_0}=f(y)}
\end{equation*}
for the left-hand side of \eqref{recursionexplicit}. For the derivatives of $\main_A$, $\main_B$, and $\main_C$,
we obtain
\begin{align*}
  \main_A &= c_A(1-\rho_{\triangs}^{-1}y)^{m_A} + O\br{(1-\rho_{\triangs}^{-1}y)^{m_A+1/4}},\\
  \main_B &= c_B(1-\rho_{\triangs}^{-1}y)^{m_B} + O\br{(1-\rho_{\triangs}^{-1}y)^{m_B+1/4}},\\
  \main_C &= c_C(1-\rho_{\triangs}^{-1}y)^{m_C} + O\br{(1-\rho_{\triangs}^{-1}y)^{m_C+1/4}}
\end{align*}
with positive constants $c_A,c_B,c_C$ and $m_A=m_B=m_C= e_1-\frac{n+1}{2} = e_2+\frac14$. For the derivatives of
$\error_B$, $\error_C$, and $\error_D$, the exponents $e_B,e_{C,1},\dotsc$ in the considerations above reduces
by $\frac{n+1}{2}$ as well. By \eqref{an} and the induction hypothesis, each term
\begin{equation*}
\left.\derivn{u}{k}P_{g_0}(y,u,z_{I_0})\derivn{u}{n+1-k}Q(y,u)\right\vert_{u=z_{I_0}=f(y)}
\end{equation*}
for $k<n$ is of the form $\ol{c}(k)(1-\rho_{\triangs}^{-1}y)^{e_1-(n+1)/2}+O\br{(1-\rho_{\triangs}^{-1}y)^{e_1-(n+1)/2+1/4}}$
with $\ol{c}(k)>0$. 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}