\errorcontextlines99 % better trace back for error messages

% yes we are using AMS-LaTEX
\iftrue

% no, we are using Springer LNCS Style
%\iffalse

%-------------------------------------------------------------------------------
% code for AMS-LaTeX follows

\documentclass[12pt]{amsart}

\def\rmdefault{ptm}% use `times' font

%-------- AMS specific macros follow -----------

\pagestyle{headings}
%\usepackage{epsf}
\usepackage{graphicx}
\usepackage{color}
%\usepackage{color}
\usepackage{cite,url}\urlstyle{rm}
%\usepackage[latin1]{inputenc}
\usepackage{amsmath, amsxtra, amsfonts, amssymb}%, nicefrac}
%\usepackage{amsthm}
%\usepackage{eucal, url}
%\usepackage{picin/picins}
%\usepackage{xspace, varioref}
%\usepackage[matrix, curve, arrow, tips, frame]{xy}
%\usepackage{pstricks, pst-node, pst-tree}
%\usepackage{mdwtab}
% ----------------------------------------

\usepackage{calc}% Needed for time stamp.
\newcounter{hours}\newcounter{minutes}
\setcounter{hours}{\the\time/60}\setcounter{minutes}{\time-\value{hours}*60}
\def\now{\ifnum\thehours<10{0}\fi\thehours:\ifnum\theminutes<10{0}\fi\theminutes}

% ----------------------------------------

\let\originalpararaph\paragraph
\def\paragraph#1{\originalpararaph{\bf #1}}

% package theorem is apparently incompatible with AMS article class (amsart)
%\usepackage{theorem}

\def\compose{\text{compose}}
\def\plan#1{G^{(#1)}}
\def\Hsym{\hat H}
\def\Nsym{\hat N}
\def\Psym{\hat P}
\def\Ssym{\hat S}

\newcommand{\Nset}{\mathbb{N}}
\newcommand{\Zset}{\mathbb{Z}}
\newcommand{\Qset}{\mathbb{Q}}
%\newcommand{\token}[1]{{\bfseries\sffamily #1}}

%\newcommand{\qed}{\hspace*{1em}\hfill
%  \setlength{\fboxsep}{0pt}\framebox[1.2ex]{\rule{0ex}{1.2ex}}}

\newcommand{\hyp}{\hspace{1pt}---\hspace{1pt}}
\newcommand{\wlg}{wlog.\xspace}
\newcommand{\dcup}{\mathrel{\dot\cup}}
\newcommand{\undef}{\mathtt{undef}}

% ----------------------------------------

\newcommand{\ie}{i.e.}
\newcommand{\Ie}{I.e.}

% ----------------------------------------

\newcommand{\prl}{\mathrel{\|}}
\newcommand{\dsj}{\mathrel{\curlyvee}}
\newcommand{\eqv}{\mathrel{\equiv}}
\newcommand{\cmp}{\mathrel{\sim}}
\newcommand{\relP}{\mathrel P}
\newcommand{\relD}{\mathrel D}
\newcommand{\nrelP}{\mathrel{\not\!\! P}}
\newcommand{\nrelD}{\mathrel{\not\!\! D}}
\newcommand{\im}{\mathrm{im}}
\newcommand{\true}{\mathtt{true}}
%\newcommand{\false}{\mathtt{false}}
\newcommand{\const}{\mathrm{const}}

\newcommand{\Path}{\mathrel{\rightsquigarrow}}
\newcommand{\token}[1]{{\bfseries\sffamily #1}}
\newcommand{\tstop}{\token{; }}
%\newcommand{\Oh}{\mathop{{\cal O}}}
\newcommand{\Oh}[1]{\mathop{{O}(#1)}}
\newcommand{\oh}[1]{\mathop{{o}(#1)}}

\newcommand{\margin}[1]{\marginpar{\footnotesize #1}}

\newcommand{\sym}{\ensuremath{{\sigma}}}

% ----------------------------------------

\newenvironment{caselist}{
  \begin{list}{\bf -}{
      \setlength{\topsep}{0.8ex}
      \setlength{\itemsep}{0pt}
      \setlength{\parsep}{0.6ex}
      \setlength{\itemindent}{0pt}
      }
    }
  {\end{list}}

\newcommand{\dominance}{{\sf dominance}\xspace}
\newcommand{\parallelity}{{\sf parallelity}\xspace}
\newcommand{\distinctness}{{\sf distinctness}\xspace}

% negative constraints
\newcommand{\NP}{{\small \sf NP}}
\newcommand{\negCons}[1]{\ensuremath{\text{neg}(#1)}}
\newcommand{\false}{\ensuremath{{\sf false}}\xspace}
%\newcommand{\PDCex}{\ensuremath{\quad \{ \; x \DISJ v, x \LT u, y \LT v, u \DISJ y \; \}}}
\newcommand{\K}[1]{\text{\small R$#1$}}
\newcommand{\KR}[1]{\text{\small R$#1$ }}
\newcommand{\RK}[1]{\text{ \small R$#1$ }}
\newcommand{\R}{\ensuremath{\mathbin{R}}} %\text{ \small R }}
\newcommand{\RR}{\ensuremath{\mathbin{R}}} %\text{ \small R }}
%\newcommand{\RR}{\text{\small R }}

%\newcommand{\prdom}{\triangleleft^+}
%\newcommand{\pirdom}{{^+}\triangleright}
%\newcommand{\pdom}{\triangleleft^*}
%\newcommand{\pidom}{{^*}\triangleright}
%\newcommand{\pdisj}{\perp}
%\newcommand{\peq}{=}
\newcommand{\prdom}{>}
\newcommand{\pirdom}{<}
\newcommand{\pdom}{\geq}
\newcommand{\pidom}{\leq}
\newcommand{\pdisj}{\nsim}
\newcommand{\peq}{=}


\newcommand{\PDOM}{\ensuremath{\mathbin{\pdom}}}
\newcommand{\PIDOM}{\ensuremath{\mathbin{\pidom}}}
\newcommand{\PRDOM}{\ensuremath{\mathbin{\prdom}}}
\newcommand{\PRIDOM}{\ensuremath{\mathbin{\pirdom}}}
\newcommand{\PEQ}{\ensuremath{\mathbin{\peq}}}
\newcommand{\PDISJ}{\ensuremath{\mathbin{\pdisj}}}
%
\newcommand{\EQ}{\ensuremath{\mathbin{\{\peq\}}}}
\newcommand{\LT}{\ensuremath{\mathbin{\{\prdom\}}}}
\newcommand{\GE}{\ensuremath{\mathbin{\{\prdom, \peq\}}}}
\newcommand{\GT}{\ensuremath{\mathbin{\{\pirdom\}}}}
\newcommand{\LE}{\ensuremath{\mathbin{\{\pirdom, \peq\}}}}
\newcommand{\LG}{\ensuremath{\mathbin{\{\pirdom, \prdom\}}}}
\newcommand{\DL}{\ensuremath{\mathbin{\{\prdom, \pdisj\}}}}
\newcommand{\DG}{\ensuremath{\mathbin{\{\pirdom, \pdisj\}}}}
\newcommand{\NL}{\ensuremath{\mathbin{\{\pirdom, \pdisj, \peq\}}}}
\newcommand{\NR}{\ensuremath{\mathbin{\{\prdom, \pdisj, \peq\}}}}
\newcommand{\DEQ}{\ensuremath{\mathbin{\{\pdisj, \peq\}}}}
\newcommand{\INEQ}{\ensuremath{\mathbin{\{\pirdom, \prdom, \pdisj\}}}}
\newcommand{\DISJ}{\ensuremath{\mathbin{\{\pdisj\}}}\xspace}
\newcommand{\NDISJ}{\ensuremath{\mathbin{\{\pirdom, \prdom, \peq\}}}}
\newcommand{\ALL}{\ensuremath{\mathbin{\{\pirdom, \prdom, \pdisj, \peq\}}}\xspace}
\newcommand{\EMPTY}{\ensuremath{\mathbin{\emptyset}}\xspace}

\newcommand{\ignore}[1]{}

% I once tried hard to make this work without changing the layout (cg)
\def\comment#1{\mbox{}\smash{\makebox[0pt]{\raisebox{1.2ex}{%
        $\blacktriangledown$}}}%
  \marginpar{\raggedright\scriptsize{\makebox[0pt][r]{{
          $\blacktriangledown\,$}}%
      #1}}}

%----------------------------------------------------

\newcommand{\mult}{�}
%\newcommand{\define}[1]{\underline{#1}}
\newcommand{\define}[1]{\emph{#1}}
\newcommand{\cut}[1]{({#1})\text{-cut}}
\newcommand{\degree}[2][{}]{\text{deg}_{#1}({#2})}
\ignore{
\newcommand{\setC}[1]{{\cal C}_{#1}}
\newcommand{\setD}[1]{{\cal D}_{#1}}
\newcommand{\setE}[1]{{\cal E}_{#1}}
\newcommand{\setF}[1]{{\cal F}_{#1}}
\newcommand{\setG}[1]{{\cal F}^0_{#1}}
\newcommand{\setH}[1]{{\cal E}^+_{#1}}
\newcommand{\setU}[1]{{\cal U}_{#1}}
\newcommand{\setL}[1]{{\cal L}_{#1}}
\newcommand{\setN}[1]{{[#1]}}
\newcommand{\setInit}{\{K_3\}}
\newcommand{\setEmpty}{\emptyset}
\newcommand{\seteq}{\cong}
\newcommand{\setplus}{\uplus}
\newcommand{\settimes}{�}
\newcommand{\setbigplus}{\biguplus}
\newcommand{\numC}[1]{|\setC{#1}|}
\newcommand{\numD}[1]{|\setD{#1}|}
\newcommand{\numE}[1]{|\setE{#1}|}
\newcommand{\numF}[1]{|\setF{#1}|}
\newcommand{\numG}[1]{|\setG{#1}|}
\newcommand{\numH}[1]{|\setH{#1}|}
\newcommand{\numU}[1]{|\setU{#1}|}
\newcommand{\numN}[1]{{#1}}
\newcommand{\numInit}{1}
\newcommand{\numEmpty}{0}
\newcommand{\numeq}{=}
\newcommand{\numplus}{+}
\newcommand{\numtimes}{\mult}
\newcommand{\numbigplus}{\sum}
}
% don't forget the ``italic correction'': \/
\newcommand{\fnull}{f\/\textsuperscript{\,0}}
\newcommand{\Fnull}{F\/\textsuperscript{\,0}}
\newcommand{\eplus}{e\/\textsuperscript{+}}
\newcommand{\Eplus}{E\/\textsuperscript{+}}

\newcommand{\distinction}[1]{#1\\}
\newcommand{\decomposition}[1]{\emph{Decomposition:} #1\\}
\newcommand{\result}[1]{\emph{Result:} #1}

\newcommand{\rootedge}[1]{{#1}}
\newcommand{\st}{\rootedge{st}}
\newcommand{\umin}{u_{\text{min}}}
\newcommand{\umax}{u_{\text{max}}}
\newcommand{\Gs}{G_s}
\newcommand{\Gt}{G_t}


\newcommand{\bijeq}{\cong}
\newcommand{\bijplus}{\uplus}
\newcommand{\bijtimes}{�}
\newcommand{\bijbigplus}{\biguplus}
\newcommand{\Cx}[1]{{\cal C}_{#1}}
\newcommand{\Ct}[1]{{\cal E}_{#1}}
\newcommand{\Cf}[1]{{\cal C}_{#1}}
\newcommand{\Df}[1]{{\cal D}_{#1}}
\newcommand{\U}[1]{{\cal U}_{#1}}
\newcommand{\cx}[1]{c_{#1}}
\newcommand{\ct}[1]{e_{#1}}
\newcommand{\cf}[1]{c_{#1}}
\newcommand{\df}[1]{d_{#1}}

\newcommand{\genC}{C(t,u)}
\newcommand{\genD}{D(t,u)}
\newcommand{\genE}{E(t,u)}
\newcommand{\genF}{F(t,u)}
\newcommand{\genG}{F\textsuperscript{0}(t,u)}
\newcommand{\genH}{E\textsuperscript{+}(t,u)}
\newcommand{\genU}{U(t,u)}
\newcommand{\genT}{C(t,t)}
\newcommand{\genf}{\frac{u}{u-t}}
\newcommand{\geng}{\frac{u}{(1-t)(u-t)}}


%----------------------------------------------------

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "0"
%%% End: 

\def\cal{\mathcal}

% dirty hack so that there is a little space above \paragraph :-P
\let\ORIparagraph\paragraph\def\paragraph{\smallskip\ORIparagraph}% \medskip is a lot

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\textwidth15cm
\textheight22cm
\hoffset-1.5truecm


%-------- end of AMS specific macros section ---


\begin{document}

\title{%
  A Direct Decomposition of 3-connected Planar Graphs % \\ in Deterministic Polynomial Time
  }

\author{Manuel Bodirsky}
\address{Manuel Bodirsky, Humboldt-Universit\"at zu Berlin, Germany}
\email{bodirsky@informatik.hu-berlin.de}
%\thanks{Manuel Bodirsky is supported by the Deutsche Forschungsgemeinschaft (DFG FOR 413/1-1).}

\author{Clemens Gr\"opl}
\address{Clemens Gr\"opl, Freie Universit\"at Berlin, Germany}
\email{groepl@inf.fu-berlin.de}
%\thanks{Clemens Gr\"opl is
%     supported by the German Federal Ministry of Education and Research within
%    the Berlin Center for Genome Based Bioinformatics (BMBF grant no.\ 031
%    2705A).}

\author{Daniel Johannsen}
\address{Daniel Johannsen, Humboldt-Universit\"at zu Berlin, Germany}
\email{johannse@informatik.hu-berlin.de}
%\thanks{Daniel is supported by \ldots}

\author{Mihyun Kang}
\address{Mihyun Kang, Humboldt-Universit\"at zu Berlin, Germany}
\email{kang@informatik.hu-berlin.de}
%\thanks{Mihyun Kang is partially supported by the Deutsche Forschungsgemeinschaft (DFG FOR 413/1-1).}


%\pagestyle{myheadings}
%\markboth{\now, \today}{\now, \today}

\keywords{Random sampling, planar graphs, algorithms}
\begin{abstract}
We present a decomposition strategy for c-nets,
i.\,e., rooted 3-connected planar maps.
The decomposition yields an algebraic equation for the number
of c-nets with a given number of vertices and a given size of the 
outer face. 
The decomposition also leads to a deterministic and polynomial time 
algorithm to sample c-nets \emph{uniformly at random}.
Using rejection sampling, we can also sample isomorphism types
of convex polyhedra, i.e., 3-connected planar graphs, uniformly at random. 

\smallskip\noindent
\textsc{R\'esum\'e.}
Nous proposons une strat\'egie de d\'ecomposition pour les cartes point\'ees
3-connexes ($c$-r\'eseaux). Cette d\'ecomposition permet d'obtenir une
\'equation alg\'ebrique pour le nombre de $c$-r\'eseaux suivant le nombre de
sommets et la taille de la face ext\`erieure. On en d\'eduit un algorithme de
complexit\'e en temps polynomiale pour le tirage al\'eatoire uniforme des
$c$-r\'eseaux. En utilisant une m\'ethode \`a rejet, nous obtenons aussi un
algorithme de tirage al\'eatoire uniforme pour les graphes planaires
3-connexes.
\end{abstract}

%The algebraic equation is of degree four and therefore
%the generating function for c-nets has an explicit description with radicals.
%From the algebraic equation we obtain a linear differential equation,
%and a single parameter recurrence, which allows to compute the number of
%c-nets for large numbers of vertices.

%\margin{MB: I would try to avoid the word ``c-net'' in the title. It sounds technical. 3-connected planar is better} 
%We present an new approach to counting formula by 
%\margin{MB: Concerning the sentence in the abstract: like it is, we would have to justify later that we can control the number of edges as well. In any case it would be fair to attribute the c-net result to Tutte, and not so much to MS}
%Mullin and Schellenberg for c-nets, by giving a direct recursion formula.
%...TODO...
%\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54A \rms (2007), Article~B54Ak\hfill}
\def\thepage{}
%
%

\section{Introduction}
\label{sec:introduction}
Three-connected planar graphs are in a one-to-one relationship to the
edge-graphs of convex polyhedra~\cite{Steinitz}.
The enumeration of such graphs has a long history. 
Already Euler attempted to find an exact formula for the number of isomorphism types of convex polyhedra~\cite{Federico}, which is still unknown.
However, since almost all such graphs have a trivial automorphism 
group~\cite{Tutte, Wormald}, 
and since all embeddings of such a graph are equivalent (due to Whitney; see e.g.~\cite{Diestel}),
the \emph{asymptotic} behavior of these numbers is the same as for the
number of \emph{c-nets}, i.e., three-connected planar maps with a distinguished
directed edge at the outer face.
The exact and the asymptotic 
number of c-nets for a given number of edges was first computed 
by Tutte~\cite{Census}.
Mullin and Schellenberg~\cite{Mullinschellen} found exact formulas in terms 
of vertices and faces. The algebraic equation derived there was analyzed 
by Bender and Richmond in~\cite{BR}, who showed that the growth constant
for the number of c-nets depending on the number of vertices is $16/27(17+7\sqrt{7}) \doteq 21.049042$.
%The algebraic equation was subsequently also used by Bender, Gao and Wormald
%to determine the asymptotic number of 2-connected planar graphs in~\cite{BGW}.

Other motivations to study c-nets come from \emph{random sampling} in theoretical
computer science%
\footnote{In the literature often the word ``generating'' is used instead of
  ``sampling''. We prefer ``sampling'' because it is more specific.}.
%
The only known algorithm to sample labeled planar graphs uniformly at random
in polynomial time requires a sampling procedure for c-nets in its ``inner
loop''~\cite{BGK03}. A sampling procedure from~\cite{genrandommaps, Airy-RSA,
Schaeffer-These} for planar maps with given numbers of vertices and edges was
applied for that step in~\cite{BGK03}, and the analysis shows that this is the
bottleneck for the performance. Recently, the sampling procedure for c-nets was
improved \cite{FPS}. But still this approach applies
rejection sampling, and therefore can only lead to \emph{expected} polynomial time
sampling procedures.
%, whereas our algorithm runs in deterministic polynomial time. 

In this paper, 
we present a new decomposition strategy for the number of c-nets 
with a given number of vertices and a given size of the outer face.
We will formulate the decomposition using the generating function for
the number of c-nets. The resulting equations can be solved with 
the quadratic method~\cite{BM, Flajolet}, 
and the generating function for the number of c-nets is
algebraic of degree four, and therefore has an explicit description with
radicals. Using the computer algebra package GFUN~\cite{gfun},
we compute a linear differential equation 
with polynomial coefficients that describes
the generating function. From that we get a single-parameter recurrence 
for its coefficients that allows 
to compute the number of c-nets with more than 100000 vertices
within reasonable time. Following the discussion in the forthcoming book of 
Flajolet and Sedgewick~\cite{Flajolet} we compute the mentioned
growth constant.

With the decomposition strategy we obtain 
the first \emph{deterministic} polynomial time sampling procedure for
c-nets.
Together with the results in~\cite{BGK03} we obtain the first
\emph{deterministic} polynomial time sampling procedure for
labeled planar graphs.
Since almost all 3-connected graphs have a trivial automorphism
group~\cite{Wormald}, this can also be used 
in a rejection sampling procedure to sample
3-connected planar graphs in \emph{expected} polynomial time.
The algorithm uses a recursive formula for c-nets on $n$ vertices
with a specified size of the outer face.
Our decomposition strategy is flexible enough to also control other parameters
of c-nets, for instance the total number of edges, faces, or the degrees
of root vertices, if needed.
From a methodological point of view, the decomposition is interesting,
since it generalizes the well-known and classical approach of Tutte
to count triangulations~\cite{TutteTri}. This direct technique
was never carried out for c-nets -- yet it is particularly suited
for the \emph{recursive method for sampling} (an
early reference is~\cite{NijenhuisWilf}; 
see~\cite{arith, Recmethod} for recent developments).

The fact that we can control the size of the outer face opens new
applications for counting \emph{unlabeled} planar graphs.
The only approach in question to enumerate unlabeled planar graphs 
exploits the connectivity structure, and was already proposed in~\cite{tensteps}. As a first step, 
we can use the result of the present paper to compute 
the number of \emph{unlabeled rooted 2-connected} planar graphs 
on a given number of edges.
Moreover, using the sampling procedure for c-nets with a specified size of the
outer face, we obtain the first expected polynomial 
time sampling procedure for unlabeled 2-connected planar graphs~\cite{BGKulab}. 
With the sampling procedures for c-nets from~\cite{FPS}
 this is not possible. 

\paragraph{Outline.} The paper is organized as follows: 
We first introduce c-nets, and
mention previous enumerative results. In Section~\ref{sect:decomp},
we describe the unique decomposition strategy for c-nets, 
which directly
translates into equations for the generating function for the number of c-nets.
In Section~\ref{sect:gf} we apply the quadratic
method to derive a single algebraic equation of degree four that defines
this generating function, and to derive a single parameter %linear 
recurrence.
%with polynomial coefficients. 
Section~\ref{sect:sampling} uses the decomposition
to sample c-nets uniformly at random. 

% $Id: definition.tex,v 1.9 2007/01/10 17:33:58 kang Exp $

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MANUEL BODIRSKY, CLEMENS GR\"OPL, DANIEL JOHANNSEN, AND
MIHYUN KANG}{\SMALL A DIRECT DECOMPOSITION OF 3-CONNECTED PLANAR GRAPHS}
%
%

\section{Planar Structures and c-nets}
\label{sect:defs}

\begin{figure}
\begin{center}
\input definition-c.pstex_t
\end{center}
\caption{A c-net on $n+k+3$ vertices}\label{fig:cnet}
\end{figure}

A \emph{map} is a graph embedded in the plane. A \emph{planar graph} 
is a graph that has an embedding in the plane.
A graph is \emph{$k$-connected} if the graph stays connected after deleting 
any $k$ vertices. By Whitney's theorem 
(see e.g.~\cite{Diestel}), all embeddings of 3-connected planar graphs
are equivalent. 
A \emph{rooted map} is a map with a distinguished directed edge $st$ (called the root edge) on the outer face. If we count rooted maps, 
we count them up to isomorphisms that map the outer face to the outer face
and the root edge to the root edge.

A \emph{c-net} is a rooted and 3-connected map on at least three vertices.
We distinguish between \emph{outer} vertices which lie on the outer face,
and \emph{inner} vertices which do not lie on the outer face.
The outer vertices include the vertices of the root $st$ and are labeled $s, t, u_1, \dots, u_k$
in clockwise order starting with the root; see Figure~\ref{fig:cnet}.\\

Starting with Tutte's pioneering work~\cite{Census},
many classes of planar maps were enumerated. 
It is possible to compute the number of
unrooted planar maps on $m$ edges~\cite{ultriconmaps, LisWalsh, WormaldMap}.
For \emph{rooted} maps, the enumeration is easier. 
The formulas for 
3-connected, 2-connected, connected, and all rooted planar maps
are related via a connectivity decomposition~\cite{Census}.
Mulling and Schellenberg~\cite{Mullinschellen} used a bijection between 3-connected rooted maps, i.e., c-nets, and \emph{quadrangulations},
which can be further decomposed,
to enumerate c-nets in terms of edges and faces (by Euler's formula, 
one can then also control the number of vertices). 
The evaluation of their formula, however, involves the evaluation
of a double summation. 
In this paper, we present a single parameter recurrence
that can be computed much faster. 
Since the generating function is algebraic, it is straightforward
to use singularity analysis (an excellent exposition of which can be found
in the forthcoming book of Flajolet and Sedgewick~\cite{Flajolet}) to reproduce 
the asymptotic results of Bender and Richmond~\cite{BR}.

%\comment{(cg) habe hier was rausgeschmissen, siehe definition.tex}
% In principle, it should be possible to use the approach of Mullin and
% Schellenberg to sample c-nets uniformly at random in deterministic polynomial
% time; however, the direct decomposition presented here leads to a simpler algorithm.
% The heart of our implementation of the recurrences
% requires just a few lines of code.

\section{Decomposition}\label{sect:decomp}
In this section we present a unique decomposition strategy for c-nets.
Informally, the idea is to \emph{remove} the root edge, 
and to describe the remaining graph in terms of smaller c-nets.
Tutte~\cite{TutteTri} applied this technique successfully to 
\emph{near-triangulations}, which generalize triangulations. 
The decomposition proposed by Tutte is simple:
Either the graph without the root edge is 3-connected,
or it is decomposed at its 2-cuts into 3-connected components.
In either case the decomposition yields one or more smaller 
near-triangulations.
The uniqueness of the decomposition is ensured by an important property 
of the simple structure of near-triangulations: 
The components of a decomposition at a 2-cut are independent, 
i.e., an arbitrary combination of near-triangulations 
can be composed to obtain a near-triangulation.

The generalization of this decomposition to c-nets faces mainly two problems.
First, the objects resulting from the decomposition (i.e., the removal of the root edge) are not necessarily c-nets.
Second, the components induced by a 2-cut are in general not independent as described before.
We solve these problems by assigning distinct generating functions 
to each type of component and by introducing a third case for the decomposition into dependent components.
This leads us to the notions of d-nets (one 3-connected component),
e-nets (there is a 2-cut that yields two dependent components) and f-nets (there is a 2-cut that yields two independent components),
which are depicted in Fig.~\ref{fig:d}.

In figures, we draw the root edge~$st$ as a directed edge. Edges that are added to the graph
are indicated as dotted lines. If a pair of vertices forms a 2-cut, we draw a
dashed circle around the two vertices. The set of inner vertices is
represented by a closed line with its size noted inside.

We formulate the decomposition in terms of generating functions.
Let $c(n,k)$ be the number of all c-nets on $n+1$ inner vertices
and $k+2$ outer vertices.
For technical reasons, we define  \emph{double rooted} c-nets
where the root can be a double edge. In particular,
the outer face of a double rooted c-net is bounded by the root $st$ and
another single undirected edge. By definition of $c(n,k)$
the number of double rooted c-nets on $n+1$ inner and two outer
vertices is $c(n,0)$.
Since every double rooted c-net can be identified with a simple c-net
by removing the undirected edge, the number of c-nets on $n+3$
vertices in total is $c(n) := c(n,0)$. Furthermore, this operation transforms
$k$ inner vertices into outer vertices, hence 
$c(n,0)= \sum_{k=1}^nc(n{-}k,k)$.
Finally, let $C(t,u):=\sum_{n\ge0}\sum_{k\ge0}c(n,k)t^nu^k$ be the
ordinary generating function for the number of c-nets, and let 
$C(t) := \sum_{n\ge0}c(n)t^n$. \\


\paragraph{Decomposition of c-nets.}
If a c-net has only three vertices ($s$, $t$, and an inner vertex) then it is
the $K_3$ with a double root and represents the only initial case of the whole
decomposition. (The decomposition terminates trivially for negative values
of~$n$ or~$k$.) Now consider c-nets on at least four vertices.  We distinguish
three disjoint cases;  they are depicted in Fig.~\ref{fig:c}.
\begin{figure}
\begin{center}
\input decomposition-c.pstex_t
\end{center}
\caption{The basic case distinction: Every c-net (except $K_3$) is either a
d-net, and an e-net, or an f-net.} \label{fig:c}
\end{figure}
\begin{enumerate}
\item[1.] After removing the root edge, the remaining graph is still three-connected.
\item[2.] The vertex~$t$ is of degree three, and there is a 2-cut in the graph
without the root edge. (The two remaining neighbors of~$t$
necessarily form a 2-cut in the graph without the root.)
\item[3.]  The vertex~$t$ is at least of degree four, and
there is a 2-cut in the graph without the root edge.
\end{enumerate}
Now let $D(n,k)$, $E(n,k)$ and $F(n,k)$ be the generating functions representing
the c-nets of the first, second and third case, with coefficients $d(n,k)$, $e(n,k)$ and
$f(n,k)$. For convenience we call these three different kind of c-nets
\emph{d-nets}, \emph{e-nets} and \emph{f-nets}.
Then the basic case distinction can be formulated as follows.
\begin{equation}\label{eqn-ctu}
C(t,u)= 1 + D(t,u) + E(t,u) + F(t,u) \,.
\end{equation}
\paragraph{Decomposition of d-nets.}
Let $G$ be a d-net, i.e., $G$ is a c-net which is 3-connected after removing the root~$st$. The decomposition of d-nets is easy. Let~$v$ be the neighbor of~$t$ (different from~$s$) on the inner face that contains the root $st$.
%\comment{suggested    correction 3}
There are two distinct cases, depicted in Fig.~\ref{fig:d}.
\begin{figure}
\begin{center}
\input decomposition-d.pstex_t
\end{center}
\caption{The decomposition of d-nets.} \label{fig:d}
\end{figure}
\begin{enumerate}
\item[1.] \distinction{The vertex~$v$ is the only vertex on the inner face of~$st$ except~$s$ and~$t$.}
\decomposition{Remove~$st$ and choose~$sv$ as new root edge.}
\result{A c-net with one inner vertex less and one outer vertex more than $G$.}
\item[2.]
\distinction{There is at least one other vertex than~$v$ on the inner face of~$st$ except~$s$ and~$t$.}
\decomposition{Remove~$st$ and insert~$sv$ as new root edge.}
\result{A d-net with one inner vertex less and one outer vertex more than $G$.}
\end{enumerate}
%\comment{suggested correction 4}
\ignore{
With exception of the initial case every double rooted c-net is a d-net. Hence
\begin{align}\label{eqn-dtu}
D(t,u) & = \frac{t}{u}(C(t,u) - C(t,0)) + \frac{t}{u}(D(t,u) - D(t,0)) \\
D(t,0) & = C(t,0) - 1 \,. 
\end{align}
}
According to the case distinction the generating function $D(t,u)$
is the sum of the generating functions $C(t,u)$ and $D(t,u)$ multiplied
by $t$ for the removed inner vertex and divided by $u$ for the additional
outer vertex. From this we have to subtract $C(t,0)$ and $D(t,0)$
(again multiplied by $t$ and divided by $u$), since the resulting graph
cannot be a double rooted c-net.
\begin{equation}\label{eqn-dtu}
D(t,u) = \frac{t}{u}(C(t,u) + D(t,u)) - \frac{t}{u}(C(t,0) + D(t,0)) \,.
\end{equation}
With exception of the initial case every c-net
with a double edges root is a d-net. Hence
\begin{equation}\label{eqn-dt0}
D(t,0) = C(t,0) - 1 \,.
\end{equation}



\paragraph{Decomposition of e-nets.}
Let $G$ be an e-net, i.e., $G$ is a c-net and~$t$ is of degree $3$.
The two neighbors of~$t$ apart from~$s$ are~$u_1$ on the outer and~$v$ on the
inner face and ${\{v,u_1\}}$ forms a 2-cut on $G$ without~$st$.
We now introduce the last two kinds of c-nets 
that appear in the decomposition.
\emph{\eplus-nets} (represented by $\Eplus(t,u)$) are defined as e-nets where
the two neighbors (other than $s$) of $t$ are connected by an edge, whereas 
\emph{\fnull-nets} (represented by $\Fnull(t,u)$) are defined as f-nets
where~$u_1$ has to be one of the cut vertices.
In the decomposition of d-nets there are four distinct cases;
they are depicted in Fig.~\ref{fig:e}.

\begin{figure}
\begin{center}
\input decomposition-e.pstex_t
\end{center}
\caption{The decomposition of e-nets.} \label{fig:e}
\end{figure}
\begin{enumerate}
\item[1.]
\distinction{There is an edge $vu_1$ in $G$.}
\result{An \eplus-net with the same number of vertices like $G$.}
\item[2.]
\distinction{There is no edge $vu_1$ and $G$ without~$t$ is 3-connected.}
\decomposition{Remove~$t$, insert the edge~$vu_1$ and insert~$su_1$ as new root edge.}
\result{A d-net with one outer vertex less than $G$.}
\item[3.]
\distinction{There is no edge $vu_1$ and $G$ without~$t$ has a 2-cut including $u_1$.}
\decomposition{Remove~$t$, insert~$vu_1$  and insert~$sv$ as new root edge.}
\result{An \fnull-net with one inner vertex less than $G$.}
\item[4.]
\distinction{There is no edge $vu_1$ and $G$ without~$t$ has a
2-cut, where~$u_1$ is no cut vertex.}
\decomposition{Remove~$t$, insert~$vu_1$ and insert~$su_1$ as new root edge.}
\result{An f-net with one outer vertex less than $G$.}
\end{enumerate}
%\comment{suggested correction 5}
The decomposition of e-nets yields the following equation where
the four terms correspond to the respective cases and
the factors $t$ and $u$ account for the removed vertices.
\begin{equation}\label{eqn-etu}
E(t,u) = \Eplus(t,u) + u~D(t,u) + t~\Fnull(t,u) + u~F(t,u) \,.
\end{equation}

\paragraph{Decomposition of \eplus-nets.}
Next, let $G$ be an \eplus-net, i.e., an e-net with an edge $vu_1$.
Again, there are four distinct cases; they are depicted in Fig.~\ref{fig:eplus}.
\begin{figure}
\begin{center}
\input decomposition-eplus.pstex_t
\end{center}
\caption{The decomposition of \eplus-nets.} \label{fig:eplus}
\end{figure}
\begin{enumerate}
\item[1.]
\distinction{The degrees of~$v$ and~$u_1$ in $G$ are both three.}
\decomposition{Remove~$t$ and~$u_1$, insert the edge $vu_2$ (which cannot exist in $G$) and insert~$sv$ as new root edge.}
\result{An e-net with one inner and one outer vertex less than $G$.}
\item[2.]
\distinction{The degree of~$v$ in $G$ is three and the degree of~$u_1$ in $G$ is at least four.}
\decomposition{Remove~$t$ and insert~$sv$ as new root edge.}
\result{An e-net with one inner vertex less than $G$.}
\item[3.]
\distinction{The degree of~$v$ in $G$ is at least four, and~$u_1$ is not a
cut-vertex of any 2-cut in $G$ without~$t$.}
\decomposition{Remove~$t$ and insert~$su_1$ as new root edge.}
\result{A c-net with one outer vertex less than $G$.}
\item[4.]
\distinction{The degree of~$v$ in $G$ is at least four, and~$u_1$ is a cut-vertex of a 2-cut in $G$ without~$t$.}
\decomposition{Remove~$t$ and insert~$sv$ as new root edge.}
\result{An \fnull-net with one inner vertex less than $G$.}
\end{enumerate}
%\comment{suggested correction 5}
In the equation defining $E(t,u)$ the four terms again
correspond to the respective cases and
the factors $t$ and $u$ account for the removed vertices.
\begin{equation}\label{eqn-eplustu}
\Eplus(t,u) = tu~E(t,u) + t~E(t,u) + u~C(t,u) + t~\Fnull(t,u) \,.
\end{equation}

\paragraph{Decomposition of f-nets and \fnull-nets.}
Let $G$ be an f-net, i.e., $G$ is a c-net where the degree of~$t$ is at least four and which
has a 2-cut after removing~$st$.
Because of planarity there exists a unique 2-cut $vu_{j+1}~(0\leq j\leq k-1)$ that is closest to~$t$
(see Figure~\ref{fig:f}).
As introduced above, $G$ is an \fnull-net if $j=0$.
$G$ without~$v$ and~$u_{j+1}$ has two components, one of which includes $t$ and~$i$ inner vertices and the other includes $s$ and~$n-i$ inner vertices.
Let $\Gt$ be the subgraph induced by~$v$,~$u_{j+1}$ and the component containing~$t$, and let $\Gs$ be the subgraph induced by~$v$,~$u_{j+1}$ 
and the component containing~$s$.
Note that the edge $vu_{j+1}$ might or might not be present in $G$.
\begin{figure}
\begin{center}
\input decomposition-f.pstex_t
\end{center}
\caption{The decomposition of f-nets and \fnull-nets.} \label{fig:f}
\end{figure}\\
\decomposition{
If~$vu_{j+1}$ is not an edge of~$G$, then insert it into both $\Gt$ and $\Gs$.
Insert~$tu_{j+1}$ as root edge into $\Gt$.
Add a new vertex~$t^\prime$ to~$\Gs$, insert the edges~$st^\prime$,~$t^\prime
v$ and~$t^\prime u_{j+1}$, and choose~$st^\prime$ to be the root edge of
$\Gs$.
}
\result{
$\Gt$ is a d-net with~$i$ inner and~$j$ outer vertices.
$\Gs$ is an \eplus-net with~$n-i$ inner and~$k-j$ outer vertices.
}
For given parameters~$i$ and~$j$ the choice whether $vu_{j+1}$ is an edge of $G$,
the choice of $\Gt$ and the choice of $\Gs$ are all independent, i.e.,
changing any of these choices in an f-net yields a different f-net with the
same parameters.
%\comment{suggested correction 5}

The later two choices account for the product of $D(t,u)$
and $\Eplus(t,u)$ in the equation defining $F(t,u)$ while the first choice
contributes a factor of two.
\begin{equation}\label{eqn-ftu}
F(t,u) = 2~D(t,u) \Eplus(t,u) \,.
\end{equation}
The decomposition for \fnull-nets is the same, and since an \fnull-net is an
f-net with $j=0$, we have
\begin{equation}\label{eqn-fnulltu}
\Fnull(t,u) = 2~D(t,0) \Eplus(t,u)
\end{equation}


\section{Generating Functions}\label{sect:gf}

\enlargethispage{10mm}
We now use the equations (\ref{eqn-ctu})--(\ref{eqn-fnulltu}) to derive an algebraic equation and an explicit description for
$C(t,u)$ and for $C(t)=C(t,0)$.
%where the coefficients of $C(t,u)$ count c-nets on $n+1$ inner and $k+2$ outer vertices and
%the coefficients $c(t)=c(n,0)$ of $C(t)$ count c-nets on $n+3$ vertices in total.
First, we eliminate the auxiliary generating functions 
$D(t,u)$, $D(t,0)$, $E(t,u)$,
$\Eplus(t,u)$, $F(t,u)$ and $\Fnull(t,u)$ within the equations in (\ref{eqn-ctu})--(\ref{eqn-fnulltu}).
%\comment{suggested correction 6}
The following list gives the order in which the functions
can be eliminated, together with the equations that are solved for
the specific function.
% and substituted in the remaining equations:
$D(t,0)$, (\ref{eqn-dt0});
$D(t,u)$, (\ref{eqn-dtu});
$F(t,u)$, (\ref{eqn-ftu});
$\Fnull(t,u)$, (\ref{eqn-fnulltu});
$E(t,u)$, (\ref{eqn-etu});
$\Eplus(t,u)$, (\ref{eqn-eplustu}).

The modified equation (\ref{eqn-ctu}) where all functions
except for $C(t,u)$ and $C(t)$ are eliminated is

\begin{align}\label{eqn-fraction}
0 =~&\frac{r_1\,C(t,u)^2  + r_2\,C(t)^2 + r_3\,C(t,u)\,C(t)
+ r_4\,C(t,u) + r_5\,C(t) + r_6}
{s_1\, C(t,u) + s_2\, C(t) + s_3}\text{\,, where} \\
r_1(t,u):=~&2 t u + 2 t^2 u + 2 t u^2 + 2 t^2 u^2 \text{\,,} \nonumber\\
r_2(t,u):=~&4 t^2 + 4 t^3 + 4 t^2 u + 4 t^3 u \text{\,,} \nonumber\\
r_3(t,u):=~&-4 t^2 - 4 t^3 - 2 t u - 6 t^2 u - 4 t^3 u - 2 t u^2 - 2 t^2 u^2 \text{\,,} \nonumber\\
r_4(t,u):=~&2 t + 2 t^2 + 4 t^3 - u + t u + 4 t^3 u + u^2 + t u^2 - 2 t^2 u^2 \text{\,,} \nonumber\\
r_5(t,u):=~&-2 t - 2 t^2 - 4 t^3 - 4 t u - 2 t^2 u - 4 t^3 u + 2 t^2 u^2 \text{\,,} \nonumber\\
r_6(t,u):=~&u + 2 t u + 2 t^2 u - t u^2 \text{\,,} \nonumber\\
s_1(t,u):=~&2 t^2 u+ 2 t^2 u^2 \text{\,,} \nonumber\\
s_2(t,u):=~&-2 t^2 - 2 t^3 + 2 t u - 2 t^2 u - 2 t^3 u - 2 t^2 u^2  \text{\,, and} \nonumber\\
s_3(t,u):=~&t + t^2 + 2 t^3 - u - t u - t^2 u + 2 t^3 u + t u^2 \text{\,.} \nonumber
\end{align}

We now look for a solution $C(t,u)$ of (\ref{eqn-fraction}), such that
the numerator equals zero for all $t$ and $u$ and the denominator
differs from zero. As $C(t,u)$ and $C(t)$ are both of degree two in
(\ref{eqn-fraction}), we can rewrite the equation as

\begin{align}\label{eqn-quadratic}
0 =~&\big(~g_1(t,u)~C(t,u) + g_2(t,u)~\big)^2 - g_3(t,u) \text{\,,\qquad where} \\
%\nonumber\\
g_1(t,u) :=~&4tu(t{+}1)(u{+}1) \text{\,,} \nonumber\\
g_2(t,u) :=~&2t{+}2t^2{+}4t^3{-}u{+}tu{+}4t^3u{+}u^2{+}tu^2{-}2 t^2u^2
             -2t(t{+}1)(u{+}1)(2t{+}u)~C(t) \text{\,,} \nonumber\\
g_3(t,u) :=~&4t^4(u{+}1)^2(4t^2{-}4tu{+}u^2{+}4t{-}4u{+}5){+}2tu(u^3{-}4 u^2{-}3u{-}2){+}u^2(u{-}1)^2 \nonumber \\
            &{+}4t^3(u^4{-}5u^3{-}9u^2{-}u{+}2){+}t^2(5u^4{-}10u^3{-}15u^2{+}4) \nonumber \\
            &+4t^2(t{+}1)^2(u{+}1)^2(2t{-}u)^2~C(t)^2
            -4t(t{+}1)(u{+}1)(4t^2{+}4t^3{+}8t^4 \nonumber\\
            &{-}4tu{-}4t^3u{+}8t^4u{-}u^2{-}5tu^2{-}2t^2u^2{-}8t^3u^2
            {+}u^3{+}tu^3{+}2t^2u^3)~C(t) \text{\,.} \nonumber %\\ \nonumber
\end{align}

Both $C(t,u)$ and $C(t)$ appear in (\ref{eqn-quadratic}), 
and we cannot solve directly for one of these functions in $t$ and $u$ only.
Setting $u=0$ we only yield the trivial equation $0=0$. 
Instead, we apply the quadratic method due to Tutte~\cite{TutteTri},
and follow the presentation in \cite{Gouldenjackson}.
We assume that there exists a function $u_t:=u(t)$ such that $g_3(t,u_t)=0$.
Equation~(\ref{eqn-quadratic}) directly yields
$0 = g_3(t,u_t) = (g_1~C + g_2)^2(t,u_t)$, hence $0 =(g_1~C + g_2)(t,u_t)$ and
then $(\frac{\partial}{\partial u}g_3)(t,u_t) = \frac{\partial}{\partial u}(g_1 C + g_2)^2 (t,u_t) 
= \big(2(g_1 C + g_2)\frac{\partial }{\partial u}(g_1 C + g_2)\big)(t,u_t) = 0$
holds as well. We now have the following pair of simultaneous equations:
$0 = g_3(t,u_t)$ and $0 = (\frac{\partial }{\partial u}g_3)(t,u_t)$, 
depending on $C(t)$, $t$ and $u$.
We eliminate $u$ by calculating the resultant, i.e., the Sylvester determinant,
of $g_3(t,u_t)$ and $(\frac{\partial }{\partial u}g_3)(t,u_t)$ with respect to $u$, 
and obtain one polynomial in $C := C(t)$ and $t$, the roots of which include
the common roots of $g_3(t,u_t)$ and $(\frac{\partial }{\partial u}g_3)(t,u_t)$; see~\cite{Flajolet} for details on resultants and generating functions.
%\comment{correction 6}
The resultant has several nontrivial factors, but only the following
factor $p(C,t)$ will be relevant for us, as
the other factors do not match the initial terms of $c(n)$.
\begin{align*}
p(C,t)=&~(8t^3{+}72t^4{+}264t^5{+}504t^6{+}528t^7{+}288t^8{+}64t^9)~C^4\\
&+(12t^2{-}228t^3{-}988t^4{-}1756t^5{-}2032t^6{-}1792t^7{-}1024t^8{-}256t^9)~C^3\\ 
&+(6t{+}218t^2{+}894t^3{+}2190t^4{+}3284t^5{+}3120t^6{+}2304t^7{+}1344t^8{+}384t^9)~C^2\\ 
&+(1{-}43t{-}337t^2{-}1021t^3{-}1828t^4{-}2404t^5{-}2128t^6{-}1344t^7{-}768t^8{-}256t^9)~C\\
&+({-}1{+}36t{+}131t^2{+}350t^3{+}540t^4{+}616t^5{+}536t^6{+}304t^7{+}160t^8{+}64t^9)\,.
\end{align*}
As the order of $p(C,t)$ as a polynomial in $C$ is four, 
and $p(C,t)=0$ yields four algebraic solutions for $C$. Comparing initial 
coefficients, we find that the following is the explicit form of the
generating function $C(t)$.

%We compare the first coefficients of the formal power series represented 
%by those solutions
%with the known initial values of $C(t)$.
%The following solution
%can be identified as the explicit algebraic form $C_0$ of $C(t)$. 
%\comment{suggested correction 6}
\ignore{
\begin{align*}
a =& -729 - 49113t - 61936t^2 - 137856t^3 + 6144t^4 + 8192t^5 \\
b =& (t - 1)(-\frac{3}{2}(32t + 17 - 7 \sqrt{7}) (32t + 17 + 7 \sqrt{7}))^\frac{3}{2} \\
s =& -3 + 2126t - 1571t^2 - 11800t^3 - 9392t^4 - 256 t^5 + 1024 t^6\\
y =& -3(2^\frac{2}{3} 4t^\frac{1}{3} (1 + t) (1 + 2 t)^3
((a + b)^\frac{1}{3} - (-1)^\frac{1}{3} (a - b)^\frac{1}{3}) +  s) \\
%C(t) =& \frac{1}{24 t (1 + t) (1 + 2 t)^3} \Big(3 (-3 + 63 t + 124 t^2 + 128 t^3 + 128 t^4 + 64 t^5) + \sqrt{y}\\ &+ \big(- 9s - y + 54 (1 + 2681 t - 46609 t^2 - 96397 t^3 + 48468 t^4 + 188304  t^5 \\
%&+ 62016 t^6 - 63488 t^7 - 32768 t^8) \frac{1}{\sqrt{y}}\big)^\frac{1}{2} \Big) \\
C(t) =&\Big(3 (-3 + 63 t + 124 t^2 + 128 t^3 + 128 t^4 + 64 t^5) + \sqrt{y}\\ &+ \big(- 9s - y + 54 (1 + 2681 t - 46609 t^2 - 96397 t^3 + 48468 t^4 + 188304  t^5 \\
&+ 62016 t^6 - 63488 t^7 - 32768 t^8)/{\sqrt{y}}\big)^\frac{1}{2} \Big) /(24 t (1 + t) (1 + 2 t)^3)\,.
\end{align*}
}
\begin{align*}%
C(t) =\,& \frac{1}{2 q_1(t)}\Big(q_2(t) + \sqrt{h(t)}+
\big(3q_3(t) - h(t) + \frac{q_4(t)}{\sqrt{h(t)}}\big)^\frac{1}{2} \Big) \\
h(t) =\,& q_1(t)\big((-1)^\frac{1}{3}(q_5(t) - q_6(t))^\frac{1}{3}
- (q_5(t) + q_6(t))^\frac{1}{3}\big)\Big(\frac{2}{t}\Big)^\frac{2}{3} + q_3(t) \\
q_1(t) =\, & 12\,t (1 + t) (1 + 2 t)^3 \\
q_2(t) =\, & 3\,(-3 + 63 t + 124 t^2 + 128 t^3 + 128 t^4 + 64 t^5) \\
q_3(t) =\, & 3\,(3 - 2126t + 1571t^2 + 11800t^3 + 9392t^4 + 256 t^5 - 1024 t^6) \\
q_4(t) =\, & 54\,(1 + 2681 t - 46609 t^2 - 96397 t^3 + 48468 t^4 + 188304  t^5 \\
&+ 62016 t^6 - 63488 t^7 - 32768 t^8) \\
q_5(t) =\, & -729 - 49113t - 61936t^2 - 137856t^3 + 6144t^4 + 8192t^5 \\
q_6(t) =\, & (t - 1)\big(-\frac{3}{2}(32t + 17 - 7 \sqrt{7}) (32t + 17 + 7 \sqrt{7})\big)^\frac{3}{2} \,.
\end{align*}%


%With the Mathematica commands Simplify[Series[$C_0, \{t, 0, 5\}$]] we can
%then compute the following
%\begin{align*}
%C(t) = 1 + 7t + 73t^2 + 879t^3 + 11713t^4 + 167423t^5 + O(t^6)
%\end{align*}

An explicit form for $C(t,u)$ can be obtained by solving equation 
(\ref{eqn-quadratic}) for $C(t,u)$,
and substituting $C(t)$ by its explicit form. 

%The explicit formulas for $C(t)$ and $C(t,u)$ 
%would fill several pages, but can be easily computed with the assistance of
%a computer algebra system like Maple or Mathematica.

%\begin{theorem}\label{thm-solution}
%Let $C(t)$, $C(t,u)$, $g_1(t,u)$, $g_2(t,u)$, $g_3(t,u)$ and $p(t)$ be defined as before, then
%\begin{enumerate}
%\item $C(t)$ is implicitly represented by $p(t)=0$,\\
%\item $p(t)=0$ can be explicitly solved for $C(t)$ as algebraic expression in $t$,
%\item $C(t,u)=-g_2(t,u)\pm\frac{\sqrt{g_3(t,u)}}{g_1(t,u)}$ can be stated
%as an algebraic expression in $t$ and $u$ by substitution $C(t)$ in $g_2$ and $g_3$.
%\end{enumerate}
%\end{theorem}

Having the algebraic equation at hand, we can apply singularity analysis:
The dominant singularity lies in the exceptional set of the
algebraic curve, and can be computed by evaluating the resultant $R$ of 
$p(C,t)$ and $\frac{\partial}{\partial C}p(C,t)$ with
respect to $C$. The solutions for $t$ in the equation $R=0$ can be computed
symbolically with Mathematica, and the smallest real solution $t_0$, where
additionally the equations 
$p(C,t_0)=0$ and $\frac{\partial}{\partial C}p(C,t_0)=0$ have
a simultaneous solution, is a dominant singularity of $C(t)$.
In this way, it is easy to compute the dominant singularity of $C(t)$, 
which is at $t_0 = 1/32(7\sqrt{7}-17)  \doteq 0.047508$ 
(that was computed before from
the equations of Mullin and Schellenberg; see ~\cite{BR}), and proves the following.

%Hence, we can reproduce the following result, 
%which is essentially from~\cite{BR}.
\begin{theorem}[essentially from~\cite{BR}]\label{thm:growthrate}
The number of c-nets $c(n)$ is in $(1/t_0)^{n+o(n)}$, 
where $1/t_0 = 16/27(17+7\sqrt{7}) \doteq 21.049042$.
\end{theorem}
%The generating function $C(t)$ has a dominant singularity at $t_0 = 1/32(7\sqrt{7}-17)$, and the growth constant for $c(n)$ is $1/t_0$.

Using the Maple package GFUN~\cite{gfun}, the algebraic equation $p(C,t)$
can be transformed automatically into a linear differential equation with
polynomial coefficients, which in turn translates to a one parameter
recurrence formula for $c_n$. Using Horner's method and this formula
we computed the value of $c(100000)$ in $100$ seconds on a PC.

\begin{theorem}\label{cor:cnrecursion}
For the coefficients $c(n)$ of $C(t)$ the following recursion holds.
{\small
\begin{align*}
c(0) =~& 1,~c(1) = 1,~c(2) = 7,~c(3) = 73,~c(4) = 879,~c(5) = 11713,\\
&c(6) = 167423,~c(7) = 2519937, \text{ and for } n\geq 8 \,, \\
c(n) =~& \Big( 
    (42147840 + 49975296(n{-}7) + 19267584(n{-}7)^2 + 2408448(n{-}7)^3)~c(n{-}7) \\
&{~}+ (291529728 + 269461504(n{-}7) + 83615232(n{-}7)^2 + 8692736(n{-}7)^3)~c(n{-}6) \\
&{~}+ (533308032 + 435701440(n{-}7) + 119431200(n{-}7)^2 + 11026784(n{-}7)^3)~c(n{-}5) \\
&{~}+ (259749888 + 220560168(n{-}7) + 59988636(n{-}7)^2 + 5361276(n{-}7)^3)~c(n{-}4) \\
&{~}+ (- 45552288 - 9821452(n{-}7) + 1941468(n{-}7)^2 + 418816(n{-}7)^3)~c(n{-}3) \\
&{~}+ (- 16057320 - 11696062(n{-}7) - 2582841(n{-}7)^2 - 180467(n{-}7)^3)~c(n{-}2) \\
&{~}+ (5063688 + 2370408(n{-}7) + 367734(n{-}7)^2 + 18930(n{-}7)^3)~c(n{-}1)
\Big ) \\
&~ \big/~(255024 + 99918(n{-}7) + 13041(n{-}7)^2 + 567(n{-}7)^3) \,.
\end{align*}
}
\end{theorem}

% (cg) 2004-11-24
% The recurrence formula has been implemented in ``compute-linear-recursion''.
% Here is the relevant part.  Be careful not to delete any digits by accident!
%
% m[n+7] = - (	(-42147840-49975296*n-19267584*n^2-2408448*n^3)*m[n]                \
% 		+(-291529728-269461504*n-83615232*n^2-8692736*n^3)*m[n+1]           \
% 		+(-533308032-435701440*n-119431200*n^2-11026784*n^3)*m[n+2]         \
% 		+(-259749888-220560168*n-59988636*n^2-5361276*n^3)*m[n+3]           \
% 		+(45552288+9821452*n-1941468*n^2-418816*n^3)*m[n+4]                 \
% 		+(16057320+11696062*n+2582841*n^2+180467*n^3)*m[n+5]                \
% 		+(-5063688-2370408*n-367734*n^2-18930*n^3)*m[n+6]                   \
% 	   )                                                                        \
% 	/                                                                           \
% 	   (255024+99918*n+13041*n^2+567*n^3);





\section{Sampling}\label{sect:sampling}
We now discuss how to use the presented decomposition to sample c-nets
uniformly at random.  
(As usual, $\Tilde O(\cdot)$ denotes growth up to logarithmic factors.)
Note that the analysis of~\cite{FPS} applies to expected running time, 
whereas our bound is deterministic. Moreover, they have parameters for vertices and faces, whereas we have parameters for the number of vertices and the size of the outer face. Thus the results are not directly comparable. 
Their upper bound is $O(n^4)$ for $n$ vertices, and reduces to $O(n)$ 
if the ratio of vertex number to face number is fixed to a constant. 
The worst case is attained for triangulations.

\begin{theorem}\label{thm:algo}
There exists a deterministic polynomial time algorithm to sample c-nets on a
given number of vertices and a given number of vertices on the outer face
uniformly at random. The algorithm runs in $\tilde O(n^5)$ time and $O(n^3)$
space.  If we allow a pre-computation, the algorithm can sample a c-net in
$\tilde O(n^2)$ time and $O(n^5)$ space.
\end{theorem}

\begin{proof}
The decomposition yields recursive counting functions for c-nets, d-nets, e-nets,
\eplus-nets, f-nets, and \fnull-nets. For all $n,k \geq 0$:\\
\begin{align*}
c(n,k) =~ &
\begin{cases}
1 & \text{if}~n=k=0 \text{\,,}\\
d(n,k) + e(n,k) + f(n,k) & \text{else.} \\
\end{cases} \\
d(n,k) =~ & c(n-1,k+1) + d(n-1,k+1) \text{\,.} \\
e(n,k) =~ & \eplus(n,k) + d(n,k-1) + \fnull(n-1,k) + f(n,k-1) \text{\,.}\\
\eplus(n,k) =~ & e(n-1,k-1) + e(n-1,k) + c(n,k-1) + \fnull(n-1,k) \text{\,.}\\
%\end{align*}
%\begin{align*}
f(n,k) =~ & 2~\sum_{i=0}^{n}\sum_{j=0}^{k} d(i,j) \mult \eplus(n-i,k-j) \text{\,.}\\
\fnull(n,k) =~ & 2~\sum_{i=0}^{n}d(i,0) \mult \eplus(n-i,k) \text{\,.}
\end{align*}
By induction on the lexicographically ordered pair $(n,k)$, the decomposition
reduces to the initial case within $O(nk)$ steps of recursion.  Hence we can
evaluate the functions using dynamic programming.  The representation size of
all computed numbers is linear, because it is bounded by the logarithm of the
number of unlabeled c-nets, which is $O(2^{O(n)})$ according to
Theorem~\ref{thm:growthrate}.  Note that the functions $d$, $e$, $\eplus$,
$f$, and $\fnull$ are at most as large as $c$ according to their definitions.
Since we employ a constant number of two-dimensional tables, the total space
requirement is $O(n^3)$.
% ... save space, no new paragraph ...
Concerning the running time, each summation runs over at most two indices, and
for each summand we have to perform one multiplication with $O(n)$ bit
numbers.  We assume an $\Oh{n\log n \log \log n}$ multiplication algorithm
(see e.g.,\ \cite{algcompl}).  Thus the running time for the computation of the
values is within $\Tilde O(n^5)$.

The values in the dynamic programming tables can be used to make the correct
probabilistic decisions in a recursive construction of c-nets, which is
essentially the inversion of the presented decomposition -- this method is
standard and known as the \emph{recursive method} for
sampling~\cite{NijenhuisWilf,arith, Recmethod}.
% ... save space, no new paragraph ...
For each entry, we scan over all the entries from which it was computed (there
are at most $n^2$ of them).  We compute partial sums in another pass over
these entries and build a balanced binary tree, where in each internal node
the maximum over its left-hand siblings is stored.  This will take $O(n^5)$
time in total, since we have $O(n^2)$ table entries, each with $O(n^2)$
dependencies, and each tree node stores an $O(n)$ bit number.  After that,
when given a random number between 1 and the maximum (i.\,e., the value of the
entry for which the tree was built), we can find the corresponding table entry
in one pass through the tree, while reading each bit of the random number only
a constant number of times, and hence in $O(n)$ time.  Then the procedure
calls itself recursively.
%
% When we have found the correct ``random sibling'', we decrement the random
% number by the partial sum over all predecessors (w.r.t.\ summation order) of
% the entry, and iterate the whole process until we hit an initial case.
%
In the case of $f$ and $\fnull$, we have to trace back two separate lines, as
the random sibling corresponds to a choice of the summation indices $i$ (for
$f$), respectively $(i,j)$ (for $\fnull$) and the actual summand is a product
of two entries (e.g., $d(i,j)$ and $\eplus(n-i,k-j)$ for $f(n,k)$ and $(i,j)$).
Note that the sum of the bit lengths of both factors is linear in the bit
length of the entry.  It follows that the total running time for generating
the decomposition tree is $\tilde O(n^2)$.
If the decomposition tree is stored appropriately, we can output the
sampled random graph in $O(n)$ time.

It is not necessary to create the binary trees physically for each entry of
the tables.  Instead, we can just redo the computations from the preprocessing
and stop if the partial sum exceeds the random number.  This way, the
algorithm uses $\tilde O(n^5)$ time and $O(n^3)$ space.
\end{proof}
\vspace{-0.15cm}

To sample unlabeled, unrooted 3-connected planar graphs uniformly at random,
we apply \emph{rejection sampling}.  That is, we generate a c-net uniformly at
random, but the resulting graph is accepted only with a probability that is
inverse proportional to the size of the orbit of the root edge together with
an incident face in the automorphism group of the graph.  (It is well-known
that the automorphism group of a planar graph can be computed efficiently, see
e.g.,~\cite{isoplan}.)  If we do not output the graph, we restart the
algorithm.  Clearly, the output of this procedure are uniform random samples
from the class of all 3-connected planar graphs.  Since a 3-connected planar
graph has with high probability a trivial automorphism group~\cite{Wormald},
the expected number of restarts is constant.

\begin{corollary}\label{cor:rejectionsampling}
  Using rejection sampling, we can sample 3-connected planar graphs using the
  algorithm of Theorem~\ref{thm:algo} in an expected constant number of rounds.
\end{corollary}



%--------------------------------------



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "0"
%%% End: 

\section{Conclusion}
Our main structural result is a new decomposition of rooted 3-connected planar
graphs, which can easily be expressed in terms of
recursive counting formulas, or equations for their 
generating functions. We use these equations 
to derive an algebraic equation of degree four
that determines the generating function for the number of rooted 
3-connected planar graphs on $n$ vertices. 
Here we apply computer algebra systems, and
also derive a single parameter recurrence formula, which allows
to compute these numbers for much larger $n$ than the previously known
formulas of Mullin and Schellenberg~\cite{Mullinschellen}.

The main algorithmic result is the first deterministic polynomial time
algorithm to sample c-nets with a given number of vertices and a given size of
the outer face uniformly at random.
Since the recurrences of the decomposition do not involve any
subtractions, the decomposition 
immediately translates into a sampling algorithm that
produces a rooted 3-connected planar graph uniformly at random. 
The recursive counting formulas were
implemented by top-down dynamic programming in C++ using the GMP library for
exact arithmetic~\cite{GMP}.
A table for small values of $n$ and $k$ is given in Figure~\ref{fig:numbers}.

% $Id: eval.tex,v 1.12 2005/05/25 14:49:44 johannse Exp $


%\section{Evaluation}
\ignore{
{%
  \def\pixipix#1#2{\rotatebox{-90}{%
      \makebox[0pt][l]{\makebox[.05\textwidth][r]{%
          \hfill\raisebox{.015\textwidth}{%
            \rotatebox{90}{\bf(#2)}}}}%
      \fbox{\includegraphics[height=\scalefac\textwidth]{eval-pix/#1}}}}%
  \def\scalefac{.46}%
  \def\scalefacrest{.027}%
\begin{figure}[t]%
  %\vspace*{-3pt}% invisible adjustment to avoid LaTeX warning message
  \centering%
  \begin{tabular}{@{}c@{\hspace*{\scalefacrest\textwidth}}c@{}}
    \pixipix{fixed-n-running-k.eps}{a} &
    \pixipix{fixed-n-running-k-logscale.eps}{b} \\
    \pixipix{fixed-k-running-n-logscale.eps}{c} &
    \pixipix{fixed-k-growthrate.eps}{d}
  \end{tabular}
  \caption{%
    Some enumeration results for up to $200$ vertices.  \ %
    (a) -- (c) show the dependency on the size of the outer face. \ %
    (d) shows the convergence of the growth rate of the number of
    c-nets~$c(n)$ on $n$~vertices.
    %(We have calculated $c(300)/c(299) \doteq 20.87$.)
    %% 20.87226790782152967578 299:298
    %% 20.87285975226366993127 300:299
  }%
  \label{fig:gnuplots2}
\end{figure}%
\begin{figure}[t]%
  %\vspace*{-3pt}% invisible adjustment to avoid LaTeX warning message
  \centering%
  \begin{tabular}{@{}c@{\hspace*{\scalefacrest\textwidth}}c@{}}
    \pixipix{fixed-n-running-k-running-m.eps}{e} &
    \pixipix{fixed-n-running-k-running-m-logscale.eps}{f} \\
%    \pixipix{plot3.eps}g &
%    \pixipix{plot4.eps}h 
  \end{tabular}
  \caption{%
    Dependency of the number of c-nets on $40$ vertices on the number of edges
    on the outer face and the total number of edges.
    }%
  \label{fig:gnuplots}
\end{figure}%
}
}

\begin{figure}
\begin{scriptsize}
\begin{center}
\begin{tabular}{@{}l@{}}
\begin{tabular}{r@{\ \ \ \vrule\ \ \ }*{7}{r@{\ \ \ }}}
$c(n,k)$  & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $n=6$ \\ % & $7$ & $8$ & $9$ & $10$ \\
\hline
$0$ & $1$ & $1$ & $7$ & $73$ & $879$ & $11713$ & $167423$  \\ %
$1$ & $1$ & $6$ & $56$ & $640$ & $8256$ & $115456$ & $1710592$ \\ %
$2$ & $1$ & $16$ & $208$ & $2848$ & $41216$ & $624384$ & $9812992$ \\ % 
$3$ & $1$ & $30$ & $560$ & $9440$ & $156592$ & $2613664$ & $44169600$ \\ % 
$4$ & $1$ & $48$ & $1240$ & $25864$ & $496944$ & $9234368$ & $169378560$ \\ %
$5$ & $1$ & $70$ & $2408$ & $61712$ & $1377600$ & $28663040$ & $574139904$ \\ %
$6$ & $1$ & $96$ & $4256$ & $132480$ & $3430528$ & $80104448$ & $1758695424$ \\ % 
$7$ & $1$ & $126$ & $7008$ & $261648$ & $7826544$ & $205083936$ & $4944057984$ \\ % 
$8$ & $1$ & $160$ & $10920$ & $483080$ & $16600944$ & $487362496$ & $12906193920$ \\ %
$9$ & $1$ & $198$ & $16280$ & $843744$ & $33111232$ & $1086226944$ & $31579350528$ \\ % 
$k=10$ & $1$ & $240$ & $23408$ & $1406752$ & $62659200$ & $2289692416$ & $72985375744$ \\ % 
\end{tabular}
~\\*
~\\*
\begin{tabular}{r@{\ \ \ \vrule\ \ \ }*{7}{r@{\ \ \ }}}
$c(n,k)$ & $7$ & $8$ & $9$ & $n=10$ \\
\hline
$0$ & $2519937$ & $39458047$ & $637446145$ & $10561615871$ \\
$1$ & $26468352$ & $423641088$ & $6966960128$ & $117148778496$ \\
$2$ & $158883840$ & $2636197888$ & $44640468992$ & $769058340864$ \\
$3$ & $756712960$ & $13136471040$ & $230851792896$ & $4102116843520$ \\
$4$ & $3095526912$ & $56624998400$ & $1039080697856$ & $19147850612736$ \\
$5$ & $11259283200$ & $218198045184$ & $4201424145408$ & $80643838062592$ \\
$6$ & $37158281984$ & $765948707328$ & $15534537453568$ & $311681600004096$ \\
$7$ & $112834665216$ & $2481031718144$ & $53154302311936$ & $1117907385569280$ \\
$8$ & $318621198720$ & $7487670554880$ & $169818439763968$ & $3751908804540416$ \\
$9$ & $843790483712$ & $21217661003264$ & $510172604564480$ & $11860405982539776$ \\
$k=10$ & $2110406347008$ & $56815355557376$ & $1449735177678848$ & $35506327812194304$ \\
\end{tabular}
\end{tabular}
\end{center}
\end{scriptsize}
%
\caption{%
  A table of $c(n,k)$ for small c-nets on up to $23$ vertices. The number
  of vertices on the outer face is~${k+2}$.  The total number of vertices
  is~${n+k+3}$.
}%
\label{fig:numbers}%
\end{figure}



It is fairly straightforward to see that the decomposition can be refined to
control more parameters of the graph, e.\,g., the number of edges, or the
degree of a root vertex~\cite{Johannsen}. 
Each parameter comes at the cost of another dimension in the tables and hence
increases the pre-computation time by a quadratic factor.  The recursive 
counting formulas with an additional parameter for the number for edges 
were also implemented, 
and we used the numbers of Mullin and Schellenberg~\cite{Mullinschellen}
to check both implementations.

The algorithm can be used to obtain a faster and now fully
deterministic polynomial time sampler for labeled planar graphs~\cite{BGK03}.
Also, 
using the rejection sampling method, we obtain an expected polynomial time
algorithm for 3-connected planar graphs (isomorphism types of convex
polyhedra).

% Manuel: for the journal version, I removed the following.
%In forthcoming work, we apply the $n$,$k$,$m$-recurrence and rejection
%sampling to generate 3-connected planar graphs with a sense-reversing
%automorphism, and unlabeled 2-connected planar graphs~\cite{BGKulab}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% (cg) 2004-11-22 late at night
%
% Moved this to Appendix since we are running out of space!
%
%\input eval.tex
%
%
%
% Note: There is still a lot of trash below ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%--------------------------------------
\ignore{%
%
% (cg) The following things are apparently not said elsewhere:
%
The recurrences for parameters $n$ and $k$, and for parameters $n$, $m$ (for
the number of edges), and $k$ were implemented ...

Figures~\ref{fig:gnuplots2} (a)--(c) show that the number of
vertices on the outer face is highly concentrated on the first few values.
The growth rate of the number of c-nets converges rapidly,
Fig.~~\ref{fig:gnuplots2}~(d).  We also investigated the interplay of the
total number of edges and the size of the outer face using the three-parameter
($n,m,k$) recurrence, see Figures~\ref{fig:gnuplots}~(a),~(b). 
%
}
%--------------------------------------




%First we can use our sampling procedure for c-nets with a given number of vertices and edges as a final step of , which provides a \emph{deterministic} polynomial time algorithm of a sampling \emph{labeled} planar graphs. %Its running time is within $\Tilde O(n^9)$ since we have at most three-dimensional tables, where the summation runs over at most four parameters and one multiplication  with large numbers should be performed.
%%\margin{we need the both parameters n, i.e., the number of vertices (since we have to deal with labels) and m, the number of edges (since we should %control the number of edges in h-core). MK}
 
%In~\cite{BGKPreprint} to sample \emph{unlabeled} 2-connected planar graphs uniformly at random a graph with a specified directed edge, called a \emph{rooted} graph, is decomposed along its connectivity structure. Whitney's classical theorem says that such a 3-connected graph has either one or two embeddings in the plane. The later case we call symmetric c-nets, which again can be decomposed along the connectivity structure of its symmetric part. 
%As a final step a sampling procedure for c-nets with a given number of edges, the number of edges on the outer face, and the degree of the root vertex is needed. 
%The sampling algorithm first generates a rooted graph uniformly at random and is restarted with a probability that is inverse proportional to the size
%of the orbit of the root. This provides an \emph{expected} polynomial time sampling algorithm for unlabeled 2-connected planar graphs.
%%\margin{The total number of edges are essential for unlabeled structure. In addition we need to control either the number of edges on the outer face for colored h-core or the degree of the $s$-pole for pole-symmetric h-core. MK}

\ignore{
We have seen a deterministic polynomial time algorithm to sample c-nets 
with a given number of vertices and a given size of the outer face 
uniformly at random. We can control other parameters of a c-net, at the cost of extra running time and space requirements.

\input eval.tex

The recurrences for parameters $n$ and $k$,
 and for parameters $n$, $m$ (for the number of edges), and $k$
were implemented by top-down dynamic programming
in C++ using the GMP library for exact arithmetic~\cite{GMP}.
They were verified against Mullin and Schellenberg's numbers~\cite{Mullinschellen}
and each other.  Figures~\ref{fig:gnuplots2} (a)--(c) show that the number of
vertices on the outer face is highly concentrated on the first few values.
The growth rate of the number of c-nets converges rapidly,
Fig.~~\ref{fig:gnuplots2}~(d).  We also investigated the interplay of the
total number of edges and the size of the outer face using the three-parameter
($n,m,k$) recurrence, see Figures~\ref{fig:gnuplots}~(a),~(b).  A table for
small values of $n$ and $k$ is given in Figure~\ref{fig:numbers}.
The program code is available from the authors.

The algorithm can be used to obtain a faster and now fully deterministic
polynomial time sampler for labeled planar graphs~\cite{BGK03}. 
Using well-known rejection sampling methods, 
we obtain an expected polynomial time algorithm
for isomorphism types of convex polyhedra.
The presented algorithm also allows to 
sample 3-connected planar graphs with a sense-reversing automorphism,
or unlabeled 2-connected planar graphs~\cite{BGKPreprint}.



%First we can use our sampling procedure for c-nets with a given number of vertices and edges as a final step of , which provides a \emph{deterministic} polynomial time algorithm of a sampling \emph{labeled} planar graphs. %Its running time is within $\Tilde O(n^9)$ since we have at most three-dimensional tables, where the summation runs over at most four parameters and one multiplication  with large numbers should be performed.
%%\margin{we need the both parameters n, i.e., the number of vertices (since we have to deal with labels) and m, the number of edges (since we should %control the number of edges in h-core). MK}
 
%In~\cite{BGKPreprint} to sample \emph{unlabeled} 2-connected planar graphs uniformly at random a graph with a specified directed edge, called a \emph{rooted} graph, is decomposed along its connectivity structure. Whitney's classical theorem says that such a 3-connected graph has either one or two embeddings in the plane. The later case we call symmetric c-nets, which again can be decomposed along the connectivity structure of its symmetric part. 
%As a final step a sampling procedure for c-nets with a given number of edges, the number of edges on the outer face, and the degree of the root vertex is needed. 
%The sampling algorithm first generates a rooted graph uniformly at random and is restarted with a probability that is inverse proportional to the size
%of the orbit of the root. This provides an \emph{expected} polynomial time sampling algorithm for unlabeled 2-connected planar graphs.
%%\margin{The total number of edges are essential for unlabeled structure. In addition we need to control either the number of edges on the outer face for colored h-core or the degree of the $s$-pole for pole-symmetric h-core. MK}
}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "0"
%%% End: 


\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{Airy-RSA}
C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria,
  \emph{Random maps, coalescing saddles, singularity analysis, and {A}iry
  phenomena}, Random Struct.\ Algorithms \textbf{19} (2001), 194--246.

\bibitem{BR}
E.A. Bender and L.B. Richmond, \emph{The asymptotic enumeration of rooted convex
  polyhedra}, J. Combin.\ Theory Ser.~B {\bf 36} (1984), 276--283.

\bibitem{Wormald}
E.A. Bender and N.C. Wormald, \emph{Almost all convex polyhedra are
  asymmetric}, Can. J. Math. \textbf{27} (1985), no.~5, 854--871.

\bibitem{BGK03}
M.~Bodirsky, C.~Gr{\"o}pl, and M.~Kang, \emph{Generating labeled planar graphs
  uniformly at random}, Proceedings of the 30th International Colloquium on
  Automata, Languages and Programming ({ICALP}'03), 2003, pp.~1095--1107.

\bibitem{BGKulab}
\bysame, \emph{Sampling unlabeled biconnected planar graphs}, Proceedings of
  the 16th Annual International Symposium on Algorithms and Computation
  ({ISAAC}'05), Springer Verlag, 2005, pp.~593--603.

\bibitem{BM}
M. Bousquet-M{\'e}lou, \emph{On (some) functional equations arising in
  enumerative combinatorics}, extended abstract for FPSAC'01, 2001.

\bibitem{algcompl}
P.~B{\"u}rgisser, M.~Clausen, and M.A. Shokrollahi, \emph{Algebraic complexity
  theory}, Grundlehren der mathematischen Wissenschaften, no. 315, Springer
  Verlag, 1997.

\bibitem{arith}
A. Denise and P. Zimmermann, \emph{Uniform random generation of
  decomposable structures using floating-point arithmetic}, Theoretical
  Computer Science \textbf{218} (1999), 233--248.

\bibitem{Diestel}
R. Diestel, \emph{Graph theory}, Springer--Verlag, New York, 1997.

\bibitem{Federico}
P.J. Federico, \emph{The number of polyhedra}, Philips Res. Repts \textbf{30}
  (1975), 220--231.

\bibitem{Recmethod}
P.~Flajolet, P.~Zimmerman, and B.~Van~Cutsem, \emph{A calculus for the random
  generation of labelled combinatorial structures}, Theoretical Computer
  Science \textbf{132} (1994), no.~1-2, 1--35.

\bibitem{Flajolet}
P. Flajolet and R. Sedgewick, \emph{Analytic combinatorics ---
  symbolic combinatorics}, book in preparation (Oct.\ 2006), and Rapport de
  recherche 4103, INRIA, 2001.

\bibitem{FPS}
E. Fusy, D. Poulalhon, and G. Schaeffer, \emph{Dissections and
  trees: applications to optimal mesh encoding and random sampling},
  Proceedings of the sixteenth annual ACM--SIAM symposium on Discrete algorithms
  (SODA'05), Society for Industrial and Applied Mathematics, 2005,
  pp.~690--699.

\bibitem{GMP}
\emph{The {GNU} multiple precision arithmetic library, version 4.1.2},
  {\tt http://swox.com/gmp/}.

\bibitem{Gouldenjackson}
I.P. Goulden and D.M. Jackson, \emph{Combinatorial enumeration}, John
  Wiley, New York, 1983.

\bibitem{isoplan}
J.E. Hopcroft and R.E. Tarjan, \emph{A $v^2$ algorithm for determining
  isomorphism of planar graphs}, Information Processing Letters \textbf{1}
  (1971), no.~1, 32--34.

\bibitem{Johannsen}
D. Johannsen, \emph{Sampling rooted 3-connected planar graphs in
  deterministic polynomial time}, Diplomarbeit, Humboldt--Universit\"at zu
  Berlin, 2006.

\bibitem{LisWalsh}
V.A. Liskovets and T.R. Walsh, \emph{Counting non-isomorphic 2-con\-nected
  planar maps}, Graph Theory Newsletter \textbf{9} (1980), no.~6, 3.

\bibitem{Mullinschellen}
R.C. Mullin and P.J. Schellenberg, \emph{The enumeration of c-nets via
  quadrangulations}, J. Combin.\ Theory \textbf{4} (1968),
  259--276.

\bibitem{NijenhuisWilf}
A.~Nijenhuis and H.S. Wilf, \emph{Combinatorial algorithms}, Academic Press
  Inc., 1979.

\bibitem{gfun}
B. Salvy and P. Zimmermann, \emph{{GFUN}: a {M}aple package for the
  manipulation of generating and holonomic functions in one variable}, ACM
  Trans.\ Math.\ Software \textbf{20} (1994), no.~2, 163--177.

\bibitem{Schaeffer-These}
G. Schaeffer, \emph{Conjugaison d'arbres et cartes combinatoires
  al{\'e}atoires}, Ph.D. thesis, Universit{\'e} Bordeaux I, 1998.

\bibitem{genrandommaps}
G. Schaeffer, \emph{Random sampling of large planar maps and convex
  polyhedra}, Proceedings of the thirty-first annual ACM symposium on theory of
  computing (STOC'99) (Atlanta, Georgia), ACM Press, May 1999, pp.~760--769.

\bibitem{Steinitz}
E.~Steinitz, \emph{Polyeder und {R}aumeinteilungen}, Encyclop\"adie der
  mathematischen Wissenschaften \textbf{3} (1922), no.~9, 1--139.

\bibitem{TutteTri}
W.T. Tutte, \emph{A census of planar triangulations}, Canad. J. Math.
  \textbf{14} (1962), 21--38.

\bibitem{Census}
\bysame, \emph{A census of planar maps}, Canad. J. Math. \textbf{15} (1963),
  249--271.

\bibitem{Tutte}
\bysame, \emph{Graph theory}, Cambridge University Press, 1984.

\bibitem{tensteps}
T.~Walsh and V.A. Liskovets, \emph{Ten steps to counting planar graphs},
  Proceedings of the Eighteenth Southeastern International Conference on
  Combinatoris, Graph Theory, and Computing, Congr. Numer. {\bf 60} (1987), 
269--277.

\bibitem{ultriconmaps}
T. Walsh, \emph{Counting non-isomorphic three-con\-nected planar maps}, J.
  Combin. Theory Ser.~B \textbf{32} (1982), 33--44.

\bibitem{WormaldMap}
N.C. Wormald, \emph{On the number of planar maps}, Canad. J. Math.
  \textbf{33} (1981), no.~1, 1--11.

\end{thebibliography}



\end{document}



