% EJC papers must begin as follows
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3}{19(3)}{2012}

% only use standard LaTeX packages
% only include essential packages

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; i.e. there must be no text protruding into the margins
% use \sloppy to avoid overly wide text
\sloppy

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\def\B{\mathcal{B}}
\def\C{\mathcal{C}}
\def\M{\mathcal{M}}
\def\Cycle{\mathscr{C}}
\def\C{M_n}
\def\ol{{\rm ol}}
\def\o{\mathrm{o}}
\def\O{\mathcal{O}}
\def\stvorcek{\ensuremath{\square}}

\def\co{\omega}
\def\md{\theta}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Matchings, cycle bases,\\ and the maximum genus of a graph}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Michal Kotrb\v{c}\'ik \qquad  Martin \v{S}koviera\\
\small Department of Computer Science\\[-0.8ex]
\small Faculty of Mathematics, Physics, and Informatics\\[-0.8ex]
\small Comenius University\\[-0.8ex]
\small Bratislava, Slovakia\\
\small\tt \{kotrbcik,skoviera\}@dcs.fmph.uniba.sk
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Mar 31, 2011}{Jun 26, 2012}{Jul 5, 2012}\\
\small Mathematics Subject Classifications: 05C10, 05C38, 05C70}

\begin{document}
%\includegraphics[width=\textwidth]{pageHeader}
\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We study the interplay between the maximum genus of a graph and
bases of its cycle space via the corresponding intersection
graph. Our main results show that the matching number of the
intersection graph is independent of the basis precisely when
the graph is upper-embeddable, and completely describe the
range of matching numbers when the graph is not
upper-embeddable. Particular attention is paid to cycle bases
consisting of fundamental cycles with respect to a given
spanning tree. For $4$-edge-connected graphs, the intersection
graph with respect to any spanning tree (and, in fact, with
respect to any basis) has either a perfect matching or a
matching missing exactly one vertex. We show that if a graph is
not $4$-edge-connected, different spanning trees may lead to
intersection graphs with different matching numbers. We also
show that there exist $2$-edge-connected graphs for which the
set of values of matching numbers of their intersection graphs
contains arbitrarily large gaps.

% keywords are optional
\bigskip\noindent \textbf{Keywords:} maximum genus; matching; cycle space; fundamental cycle
\end{abstract}



\section{Introduction}

The \textit{maximum genus} of a graph $G$, $\gamma_M(G)$, is
the largest genus of an orientable surface upon which $G$ has a
2-cell embedding. This concept was introduced by Nordhaus,
Stewart, and White \cite{NSW} in 1971, and immediately
attracted considerable attention; a survey of an early research
in this area can be found in \cite{R}. At present, maximum
genus seems to be fairly well understood, especially because it
admits a so-called good characterization in purely
combinatorial terms \cite{KOK, KG, N1, X1} and can be computed
in a polynomial time. In fact, two essentially different
polynomial-time algorithms are known, one by Glukhov \cite{G1}
and another one by Furst, Gross, and McGeoch \cite{FGM}. A
third algorithm, based on
intersection
properties of fundamental cycles, has been recently proposed by Ren, Zhang, and Li  in \cite{RZL}.
Intersection graphs of fundamental cycles, and more generally,
of cycle bases of a graph, have already been used to
characterise the maximum genus, see  \cite{G2}, \cite{N2}, and
\cite{FST}. However, matching properties of these graphs remain
largely unknown and therefore deserve further investigation.

Recall that the fundamental cycle $T(e)$ with respect to a
spanning tree $T$ of a graph $G$ is the only cycle that passes
trough a cotree edge $e$ and is contained in $T+e$. The idea of
using fundamental cycles to study the maximum genus has a
fairly long history: Glukhov \cite{G2} and Nebesk\'y \cite{N2}
determined the maximum genus of a graph by considering the
intersection graphs of bases of its cycle space. Given a graph
$G$ and a basis $\mathcal{B}$ of its cycle space, one can
define the graph $J(G,\mathcal{B})$ whose vertices are the
elements of $\mathcal{B}$ and edges join pairs of elements that
have a vertex in common. A particularly important case arises
when the basis $\mathcal{B}_T$ consisting of fundamental cycles
with respect to a spanning tree $T$ is chosen. In this
situation the intersection graph $J(G,\mathcal{B}_T)$ is simply
denoted by $G\sharp T$. The fundamental property of these
graphs is that $\gamma_M(G)$ can be expressed through their
matching numbers. The following theorem of Fu, \v Skoviera, and
Tsai \cite{FST} is a common generalization of results from
\cite{G2} and~\cite{N2}. It is stated here in a slightly
modified form, with $\nu(H)$ denoting the \textit{matching
number} of a graph~$H$, the size of a maximum matching in $H$.

\begin{theorem}\label{thm:FST}
Let $G$ be a connected graph. Then
$$
\gamma_M(G) = \min\nu(J(G,\mathcal{B}))
$$
where the minimum is taken over all bases $\mathcal{B}$ of the
cycle space of $G$. Furthermore, there is a spanning tree $T$ such
that
\begin{equation}
\label{eq:gamma_M-sharp}
\gamma_M(G) = \nu(G\sharp T).
\end{equation}
\end{theorem}

The purpose of this paper is to reveal a rather unexpected
behaviour of the matching number $\nu(J(G,\mathcal{B}))$ for
different bases of the cycle space of $G$. We show in
%Theorem~\ref{thm:main}
\hyperref[thm:main]{Theorem~\ref*{thm:main}}
 that this matching number does not
depend on the chosen basis \textit{precisely} when the graph is
upper-embeddable, that is, when $G$ admits a $2$-cell embedding
with at most two faces. In 
\hyperref[thm:range]{Theorem \ref*{thm:range}}
%Theorem~\ref{thm:range} 
we describe
the complete range of matching numbers of the intersection
graphs $J(G,\mathcal{B})$: we prove that $G$ has a basis
$\mathcal{B}$ with $\nu(J(G,\mathcal{B}))=k$ if and only if
$\gamma_M(G)\le k\le\lfloor\beta(G)/2\rfloor$, where $\beta(G)$
is the cycle rank of $G$.

The situation dramatically changes when we restrict to cycle bases
consisting of fundamental cycles. The analogue of
\hyperref[thm:main]{Theorem \ref*{thm:main}}
%Theorem~\ref{thm:main} 
is no more valid because, together with the 
upper-embeddable graphs, there also exist certain
non-upper-embed\-dable graphs $G$ for which the matching number
$\nu(G\sharp T)$ does not depend on the chosen spanning tree.
At the same time, there are graphs $G$ such that $\nu(G\sharp
T)$ does depend on the choice of the spanning tree. The edge
connectivity of such graphs is necessarily bounded above by $3$
since every $4$-edge-connected graph is upper-embeddable
\cite{J, X2}. We display an infinite family of
$2$-edge-connected graphs $(G_n)_{n\ge 1}$ such that each $G_n$
contains spanning trees $T_1$ and $T_2$ with $\nu(G_n\sharp
T_1)-\nu(G_n\sharp T_2) = n$ and any other spanning tree $T$
has either $\nu(G_n\sharp T) = \nu(G_n\sharp T_1)$ or
$\nu(G_n\sharp T) = \nu(G_n\sharp T_2)$. In other words, the
range of values of $\nu(G_n\sharp T)$ contains a gap of
size~$n$; such a gap cannot occur if general cycle bases are
considered. We further construct an infinite family of
$3$-edge-connected graphs $(H_n)_{n\ge 1}$ such that each $H_n$
contains spanning trees $T_1$ and $T_2$ with $\nu(H_n\sharp
T_1)-\nu(H_n\sharp T_2) = n$. Whether there exist
$3$-edge-connected graphs with arbitrarily large gaps in the
range of the values of $\nu(G\sharp T)$ remains open.

The maximum genus algorithm from \cite{RZL} uses the assumption
that $\nu(G\sharp T)= \gamma_M(G)$ for every spanning tree $T$
of an arbitrary graph $G$ and determines $\gamma_M(G)$ by
randomly choosing $T$ and computing the value of $\nu(G\sharp
T)$. As follows from our results, for graphs with small
edge-connectivity this approach fails.




\section{Preliminaries}
In the next few paragraphs we collect several basic definitions
needed in this paper. A \textit{circuit} in a graph $G$ is a
connected regular subgraph of valency two. A \textit{cycle} in
$G$ is a spanning subgraph having all vertices of even valency.
The set $\mathcal{C}(G)$ of all cycles of $G$ forms a vector
space over the $2$-element field $GF(2)$ with sum $C_1+C_2$
defined as the symmetric difference of the edge-sets of cycles
$C_1$ and $C_2$ and with scalar multiplication $0\cdot C=0$ and
$1\cdot C=C$. A \textit{cycle basis} of $G$ is any basis of
$\mathcal{C}(G)$. The size of any cycle basis is denoted by
$\beta(G)$ and is called the \textit{Betti number} or the
\textit{cycle rank} of $G$. Recall that every spanning tree $T$
in a connected graph $G$ gives rise to a cycle basis
$\mathcal{B}_T$ consisting of all fundamental cycles with
respect to $T$. It follows that, for connected graphs,
$\beta(G)=|E(G)|-|V(G)|+1$.

Throughout this paper the reader is assumed to be familiar with
fundamentals of topological graph theory as presented, for
example, in the monograph of Gross and Tucker~\cite{GT}. We
recall that the maximum genus $\gamma_M(G)$ of a connected
graph $G$ is the largest genus among those orientable surfaces
into which $G$ has a $2$-cell embedding. It is well known that
the maximum genus of every graph $G$ satisfies the inequality
$\gamma_M(G)\le\lfloor\beta(G)/2\rfloor$. A graph for which the
equality holds is called \textit{upper-embeddable}.

It is often convenient to express the maximum genus of a graph
$G$ through an equivalent quantity, its \textit{Betti
deficiency} $\xi(G)$. This is defined by setting
\begin{eqnarray}\label{eq:deficiency}
\xi(G) = \beta(G)-2\gamma_M(G).
\end{eqnarray}

Betti deficiency has two complementary combinatorial
characterisations. The first of them is a theorem of Xuong
\cite{X1} stating that for every connected graph $G$ one has
\begin{eqnarray}\label{eq:Xuong}
\xi(G) = \min\xi(G,T)
\end{eqnarray}
where $\xi(G,T)$ denotes the number of components of the cotree
$G-E(T)$ with odd number of edges and the minimum is taken over
all spanning trees $T$ of $G$. A spanning tree reaching this
minimum is called a \textit{Xuong tree}. Every Xuong tree also
attains the minimum of 
%formula (\ref{eq:gamma_M-sharp}) 
\hyperref[eq:gamma_M-sharp]{formula (\ref*{eq:gamma_M-sharp})}
in
%Theorem~\ref{thm:FST} 
\hyperref[thm:FST]{Theorem \ref*{thm:FST}}
(see for example \cite{CKK}) but not
necessarily vice versa. Examples of graphs with a spanning tree
that satisfies 
\hyperref[eq:gamma_M-sharp]{(\ref*{eq:gamma_M-sharp})} 
but is not a Xuong tree are easy to find.

The second characterisation
requires a little more terminology. Recall that a \textit{leaf}
of a graph is a 2-edge-connected subgraph maximal under
inclusion. A leaf is \textit{cyclically even} if its Betti
number is even, and is \textit{cyclically odd} otherwise. The
following result was proved by Kho\-men\-ko and Glukhov
\cite{KG} and independently, though in a slightly different
form, by Nebesk\'y~\cite{N1}: For every connected graph $G$ one
has
\begin{eqnarray}\label{eq:Nebesky}
\xi(G) = \max \ol(G-A) - |A|
\end{eqnarray} where $\ol(H)$
denotes the number of cyclically odd leaves of a graph $H$ and
the maximum is taken over all subsets $A\subseteq E(G)$. An
accessible proof of this formula can be found in
\cite[Theorem~2]{SS} within a broader context of signed graphs.





\section{Matchings in cycle spaces}
The following theorem is formally one of many characterisations
of upper-embeddable graphs, but in fact it is a result about
cycle spaces of  graphs. It characterises graphs in which the
intersection graphs of any two cycle bases have the same
matching number. Surprisingly, this class coincides with the
class of all upper-embeddable graphs.

\begin{theorem}\label{thm:main}
A connected graph $G$ is upper-embeddable if and only if the
intersection graphs of any two cycle bases have the same
matching number. Furthermore, if $G$ is upper-embeddable, then
the matching number coincides with
$\gamma_M(G)=\lfloor\beta(G)/2\rfloor$.
\end{theorem}

\begin{proof}
Assume that $G$ is upper-embeddable. 
\hyperref[thm:FST]{Theorem \ref*{thm:FST}}
%Theorem~\ref{thm:FST}
implies that
$\min_{\mathcal{B}}\nu(J(G,\mathcal{B}))=\gamma_M(G)=\lfloor
\beta(G)/2\rfloor$, where the minimum is taken over all bases
$\mathcal{B}$ of the cycle space of~$G$. Hence, for an
arbitrary fixed cycle basis $\mathcal{D}$ of $G$ we get
$$\nu(J(G,\mathcal{D})) \ge \min_{\mathcal{B}}
(J(G,\mathcal{B})) = \lfloor \beta(G)/2 \rfloor.$$ On the other
hand, the graph $J(G,\mathcal{D})$ has $\beta(G)$ vertices, and
therefore $$\nu(J(G,\mathcal{D}))\le\lfloor\beta(G)/2\rfloor.$$
It follows that
$\nu(J(G,\mathcal{D}))=\lfloor\beta(G)/2\rfloor$ for every
cycle basis $\mathcal{D}$ of $G$ whenever $G$ is
upper-embeddable, as claimed.

For the converse assume that $G$ is not upper-embeddable. We
intend to show that $G$ has two cycle bases $\mathcal{B}_1$ and
$\mathcal{B}_2$ such that $\nu(J(G,\mathcal{B}_1))\neq
\nu(J(G,\mathcal{B}_2))$. Let $\mathcal{B}_1$ be the basis
$\mathcal{B}_T$ consisting of the fundamental cycles with
respect to a Xuong tree $T$ of $G$  (or with respect to any
spanning tree $T$ of $G$ that attains the minimum in Theorem~1).
It follows that $\nu(G\sharp T) = \gamma_M(G)$. Take an
arbitrary maximum matching $M$ of $G\sharp T$ and choose any
two vertices $u$ and $v$ of $G\sharp T$ that are not matched by
$M$; the existence of such vertices follows from the fact that
$G$ is not upper-embeddable. Since $M$ is a maximal matching,
$u$ and $v$ are not adjacent in $G\sharp T$. Recall that $u$
and $v$ are fundamental cycles with respect to~$T$, so there
exist cotree edges $e$ and $f$ of $G$ such that $u=T(e)$ and
$v=T(f)$. Define the set $\mathcal{B}_2$ by setting
$\mathcal{B}_2=(\mathcal{B}_1-\{T(f)\})\cup\{T(e)+T(f)\}$. It
is easy to see that $\mathcal{B}_2$ is again a cycle basis and
that $J(G,\mathcal{B}_1)$ is isomorphic to a subgraph of
$J(G,\mathcal{B}_2)$ via the injective homomorphism $\phi\colon
J(G,\mathcal{B}_1)\to J(G,\mathcal{B}_2)$ which maps $T(f)$ to
$T(e)+T(f)$ and otherwise sends an element $C\in\mathcal{B}_1$
to $C\in\mathcal{B}_2$. The image $\phi(M)$ of the matching $M$
is a matching in $J(G,\mathcal{B}_2)$. Since $T(e)$ and
$T(e)+T(f)=\phi(T(f))$ have a nonempty intersection, they are
adjacent as vertices of $J(G,\mathcal{B}_2)$. Thus we can
extend the matching $\phi(M)$ of $J(G,\mathcal{B}_2)$ with the
edge joining $T(e)$ to $T(e)+T(f)$, thereby obtaining a larger
matching $M'$. Consequently,
$$\nu(J(G,\mathcal{B}_2))\ge |M'|>|M|=\nu(J(G,\mathcal{B}_1)),$$
and the result follows.
\end{proof}

Our next result strenghtens 
\hyperref[thm:main]{Theorem \ref*{thm:main}}
%Theorem \ref{thm:main} 
and provides
a complete description of the matching numbers of intersection
graphs $J(G,\mathcal{B})$ for different cycle bases of a graph
$G$. In its proof we use several concepts from matching theory;
for details we refer the reader to Lov\'asz and
Plummer~\cite{LP}. A connected component of a graph is called
\textit{odd} if it has an odd number of vertices; the number of
odd components of a graph $H$ is denoted by~$\co(H)$. The
\textit{matching deficiency} of a graph $H$, denoted~$\md(H)$,
is the number of vertices not covered by a maximum matching of
$H$, that is, $\md(H)=|V(G)|-2\nu(H)$. The \textit{Berge
Formula} states that the matching deficiency of an arbitrary
graph $G$ satisfies the equation
\begin{equation}
\label{eq:berge}
\md(G) = \max \{ \co(G-X) - |X|\},
\end{equation}
where the maximum is taken over all sets $X\subseteq V(G)$. If
$v_1,v_2,\ldots, v_n$ is the set of vertices not covered by a
maximum matching of $G$ and a set $X\subseteq V(G)$ satisfies
$\md(G)= \co(G-X) -|X|$, then the vertices $v_i$ belong to
different odd components of $G-X$. The Berge Formula and its
proof can be found in \cite{LP}.

\begin{theorem}\label{thm:range}
Let $G$ be a connected graph. Then $G$ has a cycle basis $\mathcal{B}$ with
$\nu(J(G,\mathcal{B}))=k$ if and only if $\gamma_M(G)\le
k\le\lfloor\beta(G)/2\rfloor$.
\end{theorem}

\begin{proof}
If $\mathcal{B}$ is a cycle basis with
$\nu(J(G,\mathcal{B}))=k$, then $k\ge \gamma_M(G)$ by
\hyperref[thm:FST]{Theorem \ref*{thm:FST}},
%Theorem~\ref{thm:FST}, 
and $k\le\lfloor\beta(G)/2\rfloor$,
because $J(G,\mathcal{B})$ has $\beta(G)$ vertices. This
establishes the necessary condition of the theorem.

To prove the sufficiency, we construct, for every integer $k$
with $\gamma_M(G)\le k\le\lfloor\beta(G)/2\rfloor$, a basis
$\mathcal{B}$ such that $\nu(J(G,\mathcal{B}))=k$. Assume that
the graph $G$ has Betti deficiency $\xi(G)=d$. Recall that by
\hyperref[eq:deficiency]{(\ref*{eq:deficiency})} we have $d = \beta(G) - 2\gamma_M(G)$. We
start our construction with a basis $\mathcal{B}_T$ where $T$
is a spanning tree of $G$ that attains the minimum in 
\hyperref[thm:FST]{Theorem \ref*{thm:FST}};
obviously, $\nu(J(G,\mathcal{B}_T)) =
\gamma_M(G)$.  Take an arbitrary maximum matching $M$ of
$J(G,\mathcal{B}_T)$ and note that $M$ leaves precisely $d$
vertices unmatched. Consequently, $d = \md(J(G,\mathcal{B}))$.
Denote the unmatched vertices  by $v_1,v_2, \ldots, v_{d}$. As
each $v_j$ is a fundamental cycle with respect to $T$, there
exists a cotree edge $e_j$ of $G$ such that $v_j=T(e_j)$. Let
$\mathcal{B}_0 = \mathcal{B}_T$ and let
\begin{equation}
\label{eq:B}
\mathcal{B}_{i}=\mathcal{B}_{i-1}-\{T(e_{2i})\}\cup\{T(e_{2i-1})+T(e_{2i})\}
\end{equation}
for $i=1,2,\ldots, \lfloor d/2\rfloor$. Each $\mathcal{B}_i$ is
obviously a basis of the cycle space of $G$.

As in the proof of 
\hyperref[thm:main]{Theorem \ref*{thm:main}},
it is easy to see
that $J(G,\mathcal{B}_{i-1})$ is isomorphic to a subgraph of
$J(G,\mathcal{B}_{i})$ via the injective homomorphism that
sends the vertex $T(e_{2i})$ to $T(e_{2i-1})+T(e_{2i})$ and
maps all other vertices identically. In the rest of the proof
we will slightly abuse the notation by identifying the vertices
of $J(G,\mathcal{B}_{i-1})$ with those in
$J(G,\mathcal{B}_{i})$ according to this injective
homomorphism.  As the vertex $T(e_{2i})$ in
$J(G,\mathcal{B}_{i-1})$ and the vertex $T(e_{2i-1})+T(e_{2i})$
in $J(G,\mathcal{B}_{i})$ are the only vertices where
$J(G,\mathcal{B}_{i-1})$ and $J(G,\mathcal{B}_{i})$ differ, no
confusion can occur.

Our aim is to show that $\nu(J(G,\mathcal{B}_i))=\gamma_M(G)+i$
for each $i\le \lfloor d/2\rfloor$. Clearly, it suffices to
prove the following claim.

\vspace*{2mm}

\noindent\textbf{Claim.}

(a) \textit{The graph  $J(G,\mathcal{B}_i)$ has
$\md(J(G,\mathcal{B}_i)) = d-2i$ for each $i\ge 0$.}

(b) \textit{The graph $J(G,\mathcal{B}_i)$ with $i\le \lfloor
d/2 \rfloor - 1$ has a maximum matching $M_i$ that leaves
unmatched exactly the vertices $v_{2i+1}, v_{2i+2},\ldots,
v_d$.}

\vspace*{2mm} We proceed by induction on $i$. The case $i=0$
follows from the choice of $T$ by putting $M_0 = M$. Assume
that $i > 0$. From the induction hypothesis and the
\hyperref[eq:berge]{Berge Formula (\ref*{eq:berge})}
% Berge Formula~(\ref{eq:berge}) 
we get that there is a set $X\subseteq
V(J(G,\mathcal{B}_{i-1}))$ such that $J(G,\mathcal{B}_{i-1}) -
X$ has precisely $\md(J(G,\mathcal{B}_{i-1})) + |X|$ odd
components, and the vertices $v_{2i-1}$, $v_{2i}$, \ldots,
$v_{d}$ belong to different odd components of
$J(G,\mathcal{B}_{i-1}) - X$. The definition of $\mathcal{B}_i$
implies that $v_{2i-1}$ and $v_{2i}$ are joined by an edge in
$J(G,\mathcal{B}_i)$ and therefore we can set $M_i = M_{i-1}
\cup \{v_{2i-1}v_{2i}\}$. Clearly, the vertices
$v_{2i+1},v_{2i+2},\ldots, v_{d}$ remain unmatched by $M_i$.

Now we prove that $J(G,\mathcal{B}_i)$ does not contain a
matching larger than $M_i$, that is, $\md(J(G,\mathcal{B}_{i}))
= \md(J(G,\mathcal{B}_{i-1}))-2$. Since $M_i$ leaves
$\md(J(G,\mathcal{B}_{i-1})-2$ vertices uncovered, we obtain
$\md(J(G,\mathcal{B}_{i}))\le\md(J(G,\mathcal{B}_{i-1}))-2$. On
the other hand, the
\hyperref[eq:berge]{Berge Formula (\ref*{eq:berge})}
% Berge Formula (\ref{eq:berge}) 
yields that
$$
\md(J(G,\mathcal{B}_i))=\max_{Y\subseteq V(J(G,\mathcal{B}_i))}
\co(J(G,\mathcal{B}_i))-|Y|.
$$
Notice that the difference between graphs
$J(G,\mathcal{B}_{i-1})$ and $J(G,\mathcal{B}_{i})$ is only at
the vertex~$v_{2i}$: its neighbourhood in
$J(G,\mathcal{B}_{i})$ is the union of the neighbourhoods of
$v_{2i-1}$ and $v_{2i}$ in $J(G,\mathcal{B}_{i-1})$. By the
induction hypothesis the vertices $v_{2i-1}$ and $v_{2i}$
belong to different odd components of $J(G,\mathcal{B}_{i-1}) -
X$. It follows that the graph $J(G,\mathcal{B}_{i})- |X|$ has
$\md(J(G,\mathcal{B}_{i-1})) + |X| - 2$ odd components.
Therefore
\begin{eqnarray*}
\md(J(G,\mathcal{B}_i)) &=& \max_{Y\subseteq V(J(G,\mathcal{B}_i))}
\{\co(J(G,\mathcal{B}_i)) - |Y|\}
\\
& \ge &
\md(J(G,\mathcal{B}_i)) - |X|
=
\md((J(G,\mathcal{B}_{i-1}))  - 2.
\end{eqnarray*}
This completes the induction step as well as the proof of the
theorem.
\end{proof}


We finish this section by applying 
\hyperref[thm:main]{Theorem \ref*{thm:main}}
%Theorem~\ref{thm:main} 
to $4$-edge-connected graphs.

\begin{corollary}\label{cor:4ec}
If $G$ is a $4$-edge-connected graph, then
$\nu(J(G,\mathcal{B}))=\lfloor\beta(G)/2\rfloor$ irrespectively
of the chosen basis $\mathcal{B}$ of the cycle space of $G$.
\end{corollary}

\begin{proof}
Every $4$-edge-connected graph is upper-embeddable by a result
of Jungerman \cite{J} and Xuong \cite{X2}. The conclusion now
follows from 
\hyperref[thm:main]{Theorem \ref*{thm:main}}.
\end{proof}





\section{Matchings of fundamental cycles}
In this section we focus on bases of the cycle space that only
consist of fundamental cycles. We show that the properties of
intersection graphs of fundamental cycles are in several ways
different from those that come from general cycle bases. We
start with a corollary of 
\hyperref[thm:main]{Theorem \ref*{thm:main}}.

\begin{corollary}\label{cor:ue}
If $G$ is an upper-embeddable graph, then $\nu(G\sharp
T_1)=\nu(G\sharp T_2)$ for any two spanning trees $T_1$ and $T_2$ of $G$.
\hfill $\square$
\end{corollary}

In view of 
%Theorem~\ref{thm:main}
\hyperref[thm:main]{Theorem \ref*{thm:main}}
 it is natural to ask whether
this corollary can be reversed. As the next example shows, the
answer is `no'.

\begin{example}\label{ex:fc}
Let $A_n$ be a circuit on $n\ge 3$ vertices with a loop
attached to every vertex. It is not difficult to see that
$\gamma_M(A_n) = 1$ and that $A_n$ is not upper-embeddable.
Observe that any two spanning trees $T_1$ and $T_2$ give rise
to the same cycle basis $\mathcal{B}$ which consists of the
unique circuit $C$ of length $n$ and $n$ circuits $C_i$ for
$i=1,2,\ldots, n$ of length $1$ corresponding to the loops of
$A_n$. Hence, any two spanning trees $T_1$ and $T_2$ of $A_n$
give rise to isomorphic intersection graphs $A_n\sharp T_1$ and
$A_n\sharp T_2$, all of them isomorphic to the complete
bipartite graph $K_{1,n}$. Therefore $\nu(A_n\sharp
T_1)=\nu(A_n\sharp T_2)=1$ for any two spanning trees $T_1$ and
$T_2$ of~$A_n$. \textit{This shows that the analogue of
\hyperref[thm:main]{Theorem \ref*{thm:main}}
%Theorem~{\rm \ref{thm:main}} 
for cycle bases consisting of
fundamental cycles is false.} \hfill $\blacksquare$
\end{example}


We have seen in 
\hyperref[cor:4ec]{Corollary~\ref*{cor:4ec}} that the intersection
graphs of any two cycle bases of a $4$-edge-connected graphs
have the same matching number. We now investigate the situation
in $2$-edge-connected graphs and $3$-edge-connected graphs.

Our first aim  is to show that the set of values
of the matching numbers $\nu(G\sharp T)$ for a
$2$-edge-connected graph $G$ may contain gaps of arbitrary
size. To construct the required graphs, take a path on $2n+2$
vertices and, starting from its second edge, replace every
other edge with a pair of parallel edges. Let $N_n$ denote the
resulting graph. Next, join the two pendant vertices of $N_n$
with $n$ parallel edges and denote the resulting graph by
$L_n$. Clearly, $L_n$ is $2$-edge-connected but is not
$3$-edge-connected. An example of this construction is shown in
\hyperref[fig:construction]{Figure~\ref*{fig:construction}}.

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale=.6]{l}
\hspace*{1cm}
\includegraphics[scale=.6]{n}
\caption{The graph $L_3$ (left) and its spanning subgraph
$N_3$ (right)\label{fig:construction}}
\end{center}
\end{figure}

We determine the maximum genus of $L_n$.

\begin{proposition}\label{pro:maxgen-2ec}
The graph $L_n$ has $\xi(L_n)=n$ for $n\ge 2$ even, and has
$\xi(L_n)=n-1$ for $n\ge 1$ odd. Consequently, for every
positive integer $n$ we have
$$\gamma_M(L_n) = \left\lfloor\frac{n+1}{2}\right\rfloor.$$
\end{proposition}

\begin{proof}
Consider the graph $L_n$ for a fixed $n$. Take any two adjacent
vertices that are joined by a single edge, denote this edge by
$e$, and set $A=\{e\}$. Clearly, $L_n-A$ is connected and has
either $n+1$ cyclically odd leaves if $n$ is even, or $n$
cyclically odd leaves if $n$ is odd. From 
\hyperref[eq:Nebesky]{(\ref*{eq:Nebesky})}
we then get that $\xi(L_n)\ge\ol(L_n-A)-|A|$, which equals
either $n$ for $n$ even, or equals $n-1$ for $n$ odd. On the
other hand, for any spanning tree~$S$ of $L_n-e$ the expression
\hyperref[eq:Xuong]{(\ref*{eq:Xuong})}
yields that $\xi(L_n)\le\xi(L_n,S)$, which
again equals either $n$, when $n$ is even, or equals $n-1$,
when $n$ is odd. This establishes the Betti deficiency of
$L_n$. The formula for the maximum genus of $L_n$ follows
immediately from 
\hyperref[eq:deficiency]{(\ref*{eq:deficiency})}
 and the fact that
$\beta(L_n)=2n$ for every $n\ge 1$.
\end{proof}

We now turn our attention to matchings in the intersection
graphs $L_n\sharp T$ of fundamental cycles of the graph $L_n$.

\begin{proposition}\label{pro:match-2ec}
For every positive integer $n$, the graph $L_n$ has a spanning
tree $U$ such that the graph $L_n\sharp U$ has a perfect
matching; in particular, $\nu(L_n\sharp U)=n$.
\end{proposition}

\begin{proof}
Choose any spanning tree $U$ of $L_n$ within the spanning
subgraph $N_n$. The fundamental cycles of $L_n$ with respect to
$U$ can be split into two sets $C$ and $D$ of $n$ elements each
in the following way. The set $C$ will include the fundamental
cycles corresponding to the edges from $E(L_n)-E(N_n)$ while
$D$ will have the rest. Clearly, no two members of $D$
intersect, while every element of $C$ intersects all other
elements of $C\cup D$. Thus $L_n\sharp U$ is isomorphic to the
union of the complete graph $K_n$ on the set $C$ with the
complete bipartite graph $K_{n,n}$ on the partite sets $C$ and
$D$. A perfect matching in $L_n\sharp U$ can now be constructed
by simply choosing a bijection $C\to D$ and matching an element
of $C$ to its image in $D$.
\end{proof}

The following result shows that for a $2$-edge-connected graph
$G$ not only the range of values of $\nu(G\sharp T)$ can be
nontrivial but it can also contain arbitrarily large gaps.

\begin{theorem}\label{thm:gap}
For every positive integer $n$ there exists a
$2$-edge-connected graph $G_n$ such that
$$\max_T\nu(G_n\sharp T) - \min_T\nu(G_n\sharp T) = n$$
where $T$ ranges over all spanning trees of $G_n$. Moreover,
for every spanning tree $S$ of $G_n$ the value of
$\nu(G_n\sharp S)$ coincides with one of the two extremal
values.
\end{theorem}

\begin{proof}
For each $n\ge 1$ set $G_n=L_{2n}$; clearly, $G_n$ is
$2$-edge-connected. 
\hyperref[thm:FST]{Theorem \ref*{thm:FST}}
 and
\hyperref[pro:maxgen-2ec]{Proposition~\ref*{pro:maxgen-2ec}}
 imply that for the spanning
tree $S$ described in the proof of
\hyperref[pro:maxgen-2ec]{Proposition~\ref*{pro:maxgen-2ec}}
 we have
$$
\min_T\nu(G_n\sharp T)=\nu(L_{2n}\sharp S)=\gamma_M(L_{2n})=
\lfloor(2n+1)/2\rfloor=n.
$$
On the other hand, the spanning tree $U$ from
\hyperref[pro:match-2ec]{Proposition~\ref*{pro:match-2ec}}
%Proposition~\ref{pro:match-2ec} 
gives
$$
\max_T\nu(G_n\sharp T)=\nu(L_{2n}\sharp U)=2n.
$$
It is not difficult to see that if $T$ is a spanning tree of
$L_{2n}$, then $\nu(G_n\sharp T) = 2n$. On the other hand, if
$T$ contains any edge outside $L_{2n}$, then $\nu(G\sharp T) =
n$. The result follows.
\end{proof}

We proceed to $3$-edge-connected graphs.  We intend to show
that for any integer $n$ there is a  $3$-edge-connected graph
$H_n$ such that $\nu(H_n\sharp T_1) - \nu(H_n\sharp T_2) = n$
for suitable spanning trees $T_1$ and $T_2$ of $H_n$. Denote by
$v_1, v_2,\ldots, v_{4n+4}$ the vertices along the longest path
of $N_{2n+1}$, starting from a pendant vertex of $N_{2n+1}$.
For every $i=1,2,\ldots, 2n+1$, subdivide one of the edges
between $v_{2i}$ and $v_{2i+1}$ with a vertex $u_i$. Join the
vertex $u_i$ to the vertex $u_{n+1+i}$ for every $i=1,2,\ldots,
n$ and join the vertex $u_{n+1}$ to $v_1$. Join $v_1$ to
$v_{4n+4}$ with $n$ parallel edges and denote the resulting
graph by $O_n$. It is not difficult to see that the graph $O_n$
is $3$-edge-connected. The result of this process for $n=4$ is
illustrated in
\hyperref[fig:construction_cubic]{Figure~\ref*{fig:construction_cubic}}.


\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale=1]{c5}
\caption{The graph $O_4$\label{fig:construction_cubic}}
\end{center}
\end{figure}

\begin{proposition}\label{pro:maxgen-3ec}
The graph $O_n$ has $\xi(O_n)=n$ for $n\ge 2$ even, and has
$\xi(O_n) = n-1$ for $n\ge 1$ odd. Consequently, for every
positive integer $n$ we have
$$\gamma_M(O_n) =1 + \left\lceil\frac{3n}{2}\right\rceil.$$
\end{proposition}

\begin{proof}
Consider the graph $O_n$ for a fixed $n$. Let $A$ be the set
consisting of the edges $v_1v_2$ and $v_1u_{2n+1}$ and of all
edges $u_iu_{n+1+i}$ for $1\le i \le n$. Clearly, $|A|=n+2$.
The graph $O_n - A$ is connected and has $2n+2$ cyclically odd
leaves if $n$ is even, and $2n+1$ cyclically odd leaves if $n$
is odd. From 
\hyperref[eq:Nebesky]{(\ref*{eq:Nebesky})}
%(\ref{eq:Nebesky}) 
we then get that
$\xi(O_n)\ge\ol(O_n-A)-|A|$, which equals either $n$ for $n$
even, or equals $n-1$ for $n$ odd. Let $X$ be the set of edges
of $O_n$ constructed as follows.  First, include in $X$ all
edges of $O_n$ of the form $v_iv_{i+1}$ for each $1\le i \le
4n+4$, with indices taken modulo~$4n+4$, except for of the
edges $v_{2n+1}v_{2n+2}, v_{2n+2}v_{2n+3}$, and
$v_{2n+3}v_{2n+4}$. Add to $X$ the edges $v_{2i}u_i$ for all
$1\le i \le n+1$ and $v_{2i+1}u_i$ for all $ n+1\le i \le
2n+1$. Clearly, $X$ is a spanning tree of $O_n$; for $n=4$ this
spanning tree is illustrated in
\hyperref[fig:construction_cubic_trees]{Figure~\ref*{fig:construction_cubic_trees}}~(left). 
%Figure~\ref{fig:construction_cubic_trees}
The
\hyperref[eq:Xuong]{expression~(\ref*{eq:Xuong})}
%expression (\ref{eq:Xuong})
 yields that
$\xi(O_n)\le\xi(O_n,X)$, which equals either $n$, when $n$ is
even, or equals $n-1$, when $n$ is odd. This establishes the
Betti deficiency of $O_n$. The formula for the maximum genus of
$O_n$ follows  from (\ref{eq:deficiency}) and the fact that
$\beta(O_n)=4n+2$ for every $n\ge 1$.
\end{proof}

\begin{proposition}\label{pro:match-3ec}
For every positive integer $n$, the graph $O_n$ has a spanning
tree $Y$ such that the graph $O_n\sharp Y$ has a perfect
matching; in particular, $\nu(O_n\sharp Y)=n$.
\end{proposition}

\begin{proof}
Let $Y= \{v_1v_2, v_2v_3,\ldots, v_{4n+3}v_{4n+4}, v_2u_1,
v_4u_2, \ldots, v_{4n+2}u_{2n+1} \}$. Clearly, $Y$ is a
spanning tree of $O_n$; for $n=4$ this spanning tree is
illustrated in
\hyperref[fig:construction_cubic_trees]{Figure~\ref*{fig:construction_cubic_trees}}
% Figure~\ref{fig:construction_cubic_trees}
(right). Let $A$ be the set consisting of all vertices of
$O_n\sharp Y$ that correspond to the fundamental cycles
containing the edges between $v_1$ and $v_{4n+4}$, and let $B$
be the set consisting of all vertices of $O_n\sharp Y$ that
correspond to the fundamental cycles containing the edges
$v_3u_1, v_5u_2, \ldots, v_{4n+3}u_{2n+1}$. Let $C =
V(O_n\sharp T) - (A\cup B)$. The subgraph of $O_n\sharp Y$
induced by $A$ is a complete graph on $n$ vertices, the
subgraph induced by $B$ is an edgeless graph on $2n+1$ vertices,
and the subgraph induced by $C$ is a complete graph on $n+1$
vertices. It is not difficult to see that every vertex from $A$
is adjacent to every vertex from $B\cup C$ and every vertex
from $C$ is adjacent to precisely four vertices from $B$. By
the K\"onig-Hall Theorem \cite{LP}, the subgraph induced by
$B\cup C$ contains a matching $M_1$ of size $n+1$. Let $B'$ be
the set of vertices from $B$ not covered by $M_1$. The subgraph
induced by $A\cup B'$ contains a perfect matching $M_2$, by the
K\"onig-Hall Theorem again. Clearly, $M_1 \cup M_2$ is a
perfect matching of $O_n\sharp Y$.
\end{proof}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale=0.9]{cn}
\hspace*{1cm}
\includegraphics[scale=0.9]{c4a}
\caption{Spanning trees of the graph $H_4$ (dashed):
$X$ (left) and~$Y$ (right)
\label{fig:construction_cubic_trees}}
\end{center}
\end{figure}


\begin{theorem}
For every positive integer $n$ there exists a graph
$3$-edge-connected $H_n$ such that
$$\max_T\nu(H_n\sharp T) - \min_T\nu(H_n\sharp T) = n$$
where $T$ ranges over all spanning trees of $H_n$.
\end{theorem}

\begin{proof}
For each $n\ge 1$ set $H_n=O_{2n}$; clearly, $H_n$ is
$3$-edge-connected. 
\hyperref[thm:FST]{Theorem \ref*{thm:FST}}
 and
\hyperref[pro:maxgen-3ec]{Proposition~\ref*{pro:maxgen-3ec}}
%Proposition~\ref{pro:maxgen-3ec}
 imply that for the spanning
tree $X$ described in the proof of
\hyperref[pro:maxgen-3ec]{Proposition~\ref*{pro:maxgen-3ec}}
%Proposition~\ref{pro:maxgen-3ec} 
we have
$$
\min_T\nu(H_n\sharp T)=\nu(O_{2n}\sharp X)=\gamma_M(O_{2n})=
\lfloor(2n+1)/2\rfloor=n.
$$
On the other hand, the spanning tree $Y$ from
\hyperref[pro:match-3ec]{Proposition~\ref*{pro:match-3ec}}
%Proposition~\ref{pro:match-3ec} 
gives
$$
\max_T\nu(H_n\sharp T)=\nu(O_{2n}\sharp Y)=2n.
$$
The result follows.
\end{proof}

\section{Concluding remarks}
{\bf 1.} The proof of 
\hyperref[thm:range]{Theorem \ref*{thm:range}}
%Theorem \ref{thm:range} 
and polynomial-time
algorithms for determining the maximum genus of a graph of
Furst et al. \cite{FGM} and Glukhov \cite{G1} lead to a
polynomial-time algorithm for the following problem.

\begin{center}
\begin{tabular}{|ll|}
\hline
PROBLEM: & Cycle basis matching problem \rule{0pt}{5mm}\\
INSTANCE: & Connected graph $G$, integer $k$ \\
TASK: &
Find a cycle basis $\mathcal{B}$ of $G$ such that $\nu(G,\mathcal{B})=k$,\\
& or output `NO' if such a basis does not exist.
\\
\hline
\end{tabular}
\label{problem}
\end{center}
\noindent Indeed, both maximum genus algorithms output a Xuong
tree $T$ of a graph $G$ attaining the minimum in
%Theorem~\ref{thm:FST}. 
\hyperref[thm:FST]{Theorem \ref*{thm:FST}}.
The bases $\mathcal{B}_i$ defined for
$i=0,\ldots, \lfloor \xi(G)/2\rfloor$ by equation (\ref{eq:B})
in the proof of 
\hyperref[thm:range]{Theorem \ref*{thm:range}}
%Theorem~\ref{thm:range} 
have the property that
$\nu(J(G,\mathcal{B}_i)) = \gamma_M(G) + i$ for each $i$. It
follows that if $k$ is between $\gamma_M(G)$ and $\lfloor
\beta(G)/2\rfloor$ the algorithm can output  one of the bases
$\mathcal{B}_i$ and otherwise it outputs `NO.'


\medskip\noindent
{\bf 2.} In Theorem~\ref{thm:range} we have shown that for every
graph $G$ the matching numbers $\nu(J(G,\mathcal{B}))$ fill in
the whole interval between $\gamma_M(G)$ and
$\lfloor\beta(G)/2\rfloor$. This is no longer true if the bases
restrict to fundamental cycles: as shown in
Theorem~\ref{thm:gap}, for every integer $n$ there exists a
$2$-edge-connected graph $G_n$ such that the range of values of
the matching numbers of $G_n\sharp T$ contains a gap of size
$n$. As there can be no gap if a graph is $4$-edge-connected,
by Corollary~\ref{cor:4ec}, the following problem suggests
itself.

\vspace*{3mm} \noindent{\bf Problem.} Does there exist, for any
given $n\ge 1$, a $3$-edge-connected graph $G$ such that the
range of matching numbers of $G\sharp T$ contains a gap of size
$n$?


\vskip0.8cm

\subsection*{Acknowledgements}
Research reported in this paper was
partially supported by research grants 
APVV-0223-10, VEGA 1/1005/12, and  by APVV project ESF-EC-0009-10 within the EUROCORES
Programme EUROGIGA (project GReGAS) of the European Science
Foundation.








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% we recommend using BibTeX to create a bibliography
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% then copy and past the contents of your .bbl file into this .tex file


\small

\begin{thebibliography}{99}


\bibitem{CKK} J. Chen, S. P. Kanchi, and A. Kanevsky. On the
    complexity of graph embeddings. In {\em Algorithms and
    Data Structures'}, volume 709 of 
    {\em Lecture Notes in Comput. Sci.\/}, pages 234--245, 
    Springer-Verlag, Berlin, 1993  (extended abstract). 



\bibitem{FGM} M. L. Furst, J. L. Gross, and L.~A.  McGeoch. Finding a
    maximum-genus embedding. {\em J. Assoc. Comput. Mach.}
    35: 523--534, 1988.

\bibitem{FST} H. Fu, M. \v{S}koviera, and M. Tsai. The maximum genus,
    matchings and the cycle space of a graph.
    {\em Czechoslovak Math. J.} 48:
    329--339, 1998.

\bibitem{G1} A. D. Glukhov. A contribution to the theory of
    maximum genus of a graph. In {\em Structure and Topological
    Properties of Graphs}, Inst. Mat. Akad. Nauk Ukrain. SSR,
    Kiev, 1981, 15--29 (in Russian).

\bibitem{G2} A. D. Glukhov. The maximum genus of planar graphs.
    {\em Ukrainian Math. J.} 34: 97--99, 1982 (in
    Russian).

\bibitem{GT} J.~L. Gross and T. W. Tucker. Topological Graph Theory,
    Wiley, New York, 1987.

\bibitem{J} M. Jungerman. A characterization of
    upper-embeddable graphs. {\em Trans. Amer. Math. Soc.}
    241:401--406, 1978.

\bibitem{KG} N.~P. Khomenko and A.~D. Glukhov. Single-component
    $2$-cell embeddings and maximum genus of a graph. In {\em Some
    topological and combinatorial properties of graphs}, Inst.
    Mat. Akad. Nauk Ukrain. SSR, Kiev, 1980,  5--23 (in
    Russian).

\bibitem{KOK} N.~P. Khomenko, N.~A. Ostroverkhy, and V.~A. Kuzmenko. The
    maximum genus of a graph In {\em $\phi$-Transformations of
    Graphs}, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1973,
    180--207 (in Ukrainian with English summary).

\bibitem{LP} L. Lov\'asz and M.~D. Plummer. Matching Theory,
    North-Holland, Amsterdam, 1986.


\bibitem{N1} L. Nebesk\'y L. A new characterization of the maximum
    genus of a graph.
{\em Czechoslovak Math. J.} 31:604--613, 1981.


\bibitem{N2} L. Nebesk\'y L. Characterizing the maximum genus of a
    connected graph. 
{\em Czechoslovak Math. J.} 43:177--183, 1993.


\bibitem{NSW} E.~A.~Nordhaus, B.~M.~Stewart, and A.~T.~White. On the
    maximum genus of a graph. 
{\em J. Combinatorial Theory Ser. B} 11:258--267, 1971.


\bibitem{RZL} H.~Ren, H.~T.Zhao, H.~L.~Li. Fundamental cycles and
    graph embeddings. 
{\em Sci. China Ser.~A} 52:1920--1926, 2009.


\bibitem{R} R.~D.~Ringeisen. Survey of results on the maximum
    genus of a graph. {\em J. Graph Theory} 3:1--13, 1979.


\bibitem{SS} J.~\v{S}ir\' a\v{n} and M.~\v{S}koviera. 
    Characterization of the maximum genus of a signed
    graph. {\em J. Combinatorial Theory Ser. B} 52:124--146, 1991.


\bibitem{X1} N.~H.~Xuong. How to determine the maximum genus of a
    graph. {\em J. Combinatorial Theory Ser. B} 26:217--225, 1979.


\bibitem{X2} N.~H.~Xuong. Upper-embeddable graphs and related
    topics. {\em J. Combinatorial Theory Ser. B} 26:226--232, 1979.

\end{thebibliography}

\end{document}

