
\documentstyle[12pt,fleqn]{article}

%Definizioni Latex Anna 

\newtheorem{Definition}{\bf Definition}[section]
\newtheorem{Example}[Definition]{\bf Example}
\newtheorem{Remark}[Definition]{\bf Remark}
\newtheorem{Lemma}[Definition]{\bf Lemma}
\newtheorem{Theorem}[Definition]{\bf Theorem}
\newtheorem{Corollary}[Definition]{\bf Corollary}
\newtheorem{Proposition}[Definition]{\bf Proposition}

\textwidth 15.6 cm   %**************
\textheight 20 cm  %**************
\oddsidemargin 0.4 cm  %**************
\topmargin 0.6 cm  %**************


\newcommand{\bform}{\begin{displaymath}}
\newcommand{\eform}{\end{displaymath}\smallskip}
\newcommand{\beqn}[1]{\begin{equation}\label{#1}}
\newcommand{\eeqn}{\end{equation}\smallskip}
\newcommand{\beqna}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\eeqna}{\end{eqnarray}\smallskip}
\newcommand{\beqnan}{\begin{eqnarray*}}
\newcommand{\eeqnan}{\end{eqnarray*}\smallskip}
\newcommand{\tr}[1]{#1^{\scriptscriptstyle T}}
\newcommand{\rif}[1]{(\ref{#1})}
\newcommand{\vect}[2]{\left(\begin{array}{c} #1\\#2 \end{array}\right)}
\newcommand{\done}{\hfill$\Box$\par}

\def\Re{I\!\!R}
\def\gt{>}
\def\lt{<}
\def\sp{\;\;}
\def\wug{=^{\!\!\!\!\!^{2}}}
\def\wnug{\ne^{\!\!\!\!\!^{2}}}
\def\prec{<^{\!\!\!\!\!^{L}}}
\def\prece{\le^{\!\!\!\!\!^{L}}}


\begin{document}


\begin{titlepage}
\title{\large {\bf A Theory of Pfaffian Orientations I: 
 Perfect Matchings and Permanents.}} 
\author{
       \normalsize {\bf Anna Galluccio}\\
       {\normalsize Istituto di Analisi dei Sistemi ed} \\
       {\normalsize Informatica - CNR}\\ 
       {\normalsize viale Manzoni 30}\\
       {\normalsize 00185 Roma}\\
        {\normalsize ITALY} 
\and
\thanks{Supported by DONET,  GACR 0194 and GAUK 194}
   \normalsize {\bf Martin Loebl}\\
   {\normalsize Department of Applied Mathematics }\\
   {\normalsize Charles University, Praha }\\
   {\normalsize Praha }\\
   {\normalsize CZECH REPUBLIC}
}

\maketitle

\begin{abstract}
Kasteleyn stated that the generating function
of the perfect matchings of a graph of genus $g$ may be written as
a linear combination of $4^g$ Pfaffians. 
Here we prove this statement. As a consequence we present a combinatorial
way to compute permanents of square matrices.
 
Other consequences will be presented in a forthcoming paper.
\end{abstract}

\end{titlepage}

\section{Introduction}
We present a theory of Pfaffian orientations of graphs, introduced by 
Kasteleyn (\cite{kast,KAST1,KAST2}). 
Our approach is an extension of the treatment of toroidal rectangular 
lattices (see \cite{kw, pw, kast,KAST1,KAST2}).
The case of general toroidal graphs was also studied by Barahona 
(\cite{b2}).
As a consequence, we present a new technique to compute permanents of
square matrices, which completes the Polya's scheme (\cite{Polya}). 

$G=(V,E)$  will always be a graph and $x_e$ will be a variable 
associated with each edge $e$ of $G$. We let $x=(x_e:e\in E)$ and 
for $M\subset E$ let $x(M)$ denote the product of the variables of 
the edges of $M$. 
An orientation of a graph $G$ is a digraph obtained from $G$ by 
fixing an orientation of each edge of $G$.

Let $A\Delta B$ denote the symmetric difference of the sets $A$ 
and $B$ and let $a\wug b$ denote $a=b$ modulo $2$. 



\begin{Definition}
The {\it generating function
 of the perfect matchings} of $G$ is polynomial ${\cal P}(G,x)$ equal
 to the sum of $x(P)$ over all perfect matchings $P$ of $G$.
\end{Definition}


\begin{Definition}
Let $G$ be a graph and let $D$ be an orientation of $G$. Let $M$ be a perfect
matching of $G$. For each perfect matching $P$ of $G$ let
$sgn(D,M\Delta P)=(-1)^n$ where $n$ equals to the number of 
clockwise even alternating cycles
of $M\Delta P$, and let ${\cal P}(D,M)$ equals to the sum of
$sgn(D,M\Delta P) x(P)$ over all perfect matchings $P$ of $G$.
\end{Definition}


\begin{Definition}
Let $G=(V,E)$ be a graph with $2n$ vertices and $D$ be an orientation of $G$. 
Denote by $A(D)$
the skew-symmetric matrix with the rows and the columns indexed by 
$|V|$, where $a_{vw}=x_{(v,w)}$ in case $(v,w)$ is an arc of $D$, 
$a_{vw}= -x_{(v,w)}$ in case $(w,v)$ is an arc of $D$, and $a_{vw}=0$
otherwise. 

The {\it Pfaffian} of the skew-symmetric matrix $A(D)$ is defined as 
 
$$Pf(A(D))=\sum_{P} s^*(P)a_{i_1j_1} \cdots a_{i_nj_n}$$
 
\noindent
where $P=\{\{i_1j_1\},\cdots,\{i_nj_n\}\}$ is a partition of the 
set $\{1,\dots,2n\}$ into pairs, $i_k<j_k$ for $k=1,\dots,n$, and 
$s^*(P)$ equals to the sign 
of the permutation $(i_1j_1\dots i_nj_n)$.

Each nonzero term of the expansion of the Pfaffian of $A(D)$ 
equals $x(P)$ or $-x(P)$ where $P$ is a perfect matching of $G$. 
Let $s(D,P)$ equal the sign of the term $x(P)$ so that 

$$Pf(A(D))=\sum_{P} s(D,P)x(P)$$ 

\end{Definition}

The following theorem was proved by Kasteleyn (\cite{KAST2}). 

\begin{Theorem} 
\label{Kastel}
Let $G$ be a graph and $D$ an orientation of $G$. Let $P,M$ be two 
perfect matchings of $G$. Then
$$s(D,P)=s(D,M)sgn(D,M\Delta P)$$.

Hence, 
$$Pf(A(D))=\sum_{P} s(D,P)x(P)=s(D,M)\sum_{P} sgn(D,M\Delta P)x(P)=
s(D,M){\cal P}(D,M)$$.
\end{Theorem}

The following theorem is well-known (see \cite{Cayley}).

\begin{Theorem}
\label{Cayley}
Let $G$ be a graph and let $D$ be an orientation of $G$. 

Then $Pf^2(A(D)) = det(A(D))$.
\end{Theorem}

\bigskip\noindent
{\bf Remark.} This theorem has an algorithmic application: if the edge-set of 
$G$ is partitioned into a bounded number of classes 
and the variables $x_e$ are equal in each class, then 
${\cal P}(D,M)$ and $Pf(A(D))$ may be determined efficiently.

Let $M=\{\{i_1j_1\},\dots,\{i_nj_n\}\}$, $i_k<j_k$, be a perfect 
matching of $G$. Let $x'$ be defined as follows: $x'_e=x_e$, 
if $e\notin M$ and $x'_f=x_fz$, if $f\in M$, $z$ is a new 
variable. 
Let $A'$ be the matrix obtained from $A(D)$ by replacing each 
$x_e$ by $x'_e$. Using Gaussian 
elimination we can express efficiently $det(A')$ as a rational function, 
i.e. a ratio of two polynomials. Since $det(A')$ is a 
polynomial, its coefficients can be determined efficiently from the 
rational function. We can view $det(A')$ as a polynomial 
$det(A')(x')$ or as a polynomial $det(A')(x,z)$. 
By Theorem~\ref{Cayley}, $Pf(A')(x,z)=\pm \sqrt{det(A')(x,z)}$. Hence we can 
determine efficiently a polynomial $Q(x,z)$ such that $Pf(A')(x,z)=\pm 
Q(x,z))$. Note that ${\cal P}(D,M)=\pm Q(x,1)$. 

There is exactly one monomial in $Q(x,z)$ containing $z^n$ and its 
coefficient is $+1$ or $-1$. Let $Q'(x,z)$ be the unique polynomial 
such that $Q'(x,z)=Q(x,z)$ or $Q'(x,z)=-Q(x,z)$ and the coefficient of 
$Q'(x,z)$ of the term containing $z^n$ equals to $+1$. 
We have ${\cal P}(D,M)=+Q'(x,1)$. Moreover, $Pf(A(D))=s(D,M){\cal 
P}(D,M)$ and $s(D,M)=s^*(M)t^*(M)$ where $t^*(M)$ equals to the 
product of the signs of the elements $a_{i_kj_k}$ of the matrix 
$A(D)$ such that $i_kj_k\in M$. 
Hence ${\cal P}(D,M)$ and $Pf(A(D))$ may be determined efficiently.

\bigskip\noindent
Kasteleyn (\cite{KAST2}) introduced the following notion.

\begin{Definition}
A graph $G$ is called {\it Pfaffian} if it has a {\it Pfaffian} orientation,
i.e. an orientation such that each alternating cycle with respect 
to an arbitrary fixed perfect matching $M$ of $G$ is clockwise odd.
\end{Definition}

\medskip
Hence if a graph $G$ has a Pfaffian orientation $D$ then 
$s(D,P)$, $P$ perfect matching of $D$, are equal and 
${\cal P}(G,x)^2 = Pf^2(A(D))= det(A(D))$.

Kasteleyn (\cite{KAST2}) also observed that the planar graphs have a Pfaffian 
orientation.

\begin{Theorem}
\label{plpf}
Each planar graph has a Pfaffian orientation.
\end{Theorem}
\medskip\noindent
{\bf Proof.} Let $G$ be a planar graph, and let $M$ be its perfect matching.
Consider $G$ drawn on the plane.
Orient edges of $G$ so that each face, except possibly the outer one,
is clockwise odd. Each such face `encircles' no vertex 
of $G$. Observe that the orientation has the property
that a cycle $C$ of $G$ is clockwise odd if and only if $C$ encircles an
even number of vertices.
Each alternating cycle with respect to $M$ encircles an even number of vertices
and hence it is clockwise odd.
\done





\section{The Perfect Matchings}



\begin{Definition}
We define surface $S_g$ , $g$ positive integer, as follows.
It consists of a {\it base} $B_0$ and $2g$ {\it bridges}
$B^i_j$, $i=1,...,g$ and $j=1,2$. $B_0$ is a convex $4g$-gon with vertices
$a_1, ...,a_n$, $n=4g$, numbered clockwise. Bridge $B^i_1$ is a $4$-gon
with vertices $x^i_1, x^i_2, x^i_3, x^i_4$ numbered clockwise . It is glued 
with $B_0$ so that edge $(x^i_1,x^i_2)$ of $B^i_1$ is identified with
edge $(a_{4(i-1)+1},a_{4(i-1)+2})$ of $B_0$ and edge $(x^i_3,x^i_4)$ of 
$B^i_1$ is identified with edge $(a_{4(i-1)+3},a_{4(i-1)+4})$ of $B_0$ . 

Bridge $B^i_2$ is a $4$-gon with vertices $ y^i_1, y^i_2, y^i_3, y^i_4$ 
numbered clockwise. It is glued 
 with $B_0$ so that edge $(y^i_1,y^i_2)$ of $B^i_2$ is identified with
 edge $(a_{4(i-1)+2},a_{4(i-1)+3})$ of $B_0$ and edge $(y^i_3,y^i_4)$ of 
$B^i_2$ is identified with
 edge $(a_{4(i-1)+4},a_{4(i-1)+5 mod 4g})$ of $B_0$.
\end{Definition}

\medskip
The definition of surface $S_g$ corresponds to the usual definition
 of an orientable surface of genus $g$ in the following sense.
 Orientable surface $O_g$ of genus $g$ may be obtained from $S_g$
 as follows: for each bridge $B$, glue together the two segments in 
 which $B$ intersects the boundary of $B_0$, and delete $B$. 

\begin{Definition}
\label{embed}
We say that a graph $G$ is a $g$-graph if it may be drawn on $S_g$
 so that all the vertices belong to the base $B_0$, and 
 each edge uses at most one bridge. 
The set of the edges drawn on the base will be denoted by $E_0=E_0(G)$ and
 the set of edges drawn on bridge $B^i_j$ will be denoted by $E^i_j=E^i_j(G)$.
 
 If moreover the following conditions are satisfied then we say
 that $G$ is a {\it proper $g$-graph}.
\begin{enumerate}
\item[1.]
 The outer face of the subgraph embedded on $B_0$ is a cycle,
 and it is embedded on the boundary of $B_0$,
\item[2.]
 Each vertex is incident with at most one edge out of $E_0$,
\item[3.]
 The subgraph embedded on $B_0$ has a perfect matching.
\end{enumerate}

  If $G$ is a proper $g$-graph then we denote by $C_0$
 the cycle which forms the outer face of $E_0$, and we denote
 by $M_0$ a perfect matching of the subgraph of $G$ embedded
 on $B_0$.
\end{Definition}

\medskip

For each $g$-graph we fix its drawing on $S_g$.

\begin{Definition}
Let $G=(V,E)$ be a proper $g$-graph. The graphs $G_0=(V,E_0)$ and 
$G^i_j=(V,E_0 \cup E^i_j)$ are planar. 
We define orientations of $G_0$ and $G^i_j$ as follows: 
orientation $D_0$ of $G_0$ is Pfaffian and such that each face of 
$G_0$ is clockwise odd (as in the proof of Theorem~\ref{plpf}).
Next we draw $G^i_j$ 
 on the plane so that the drawing of $G_0$ is unchanged,
 and edge $(x^i_1,x^i_4)$ ($(y^i_1,y^i_4)$ respectively)of $B^i_j$
 belongs to the outer face
 of the drawing of $G^i_j$. Now complete $D_0$ to an orientation
 of $G^i_j$ so that each face is clockwise odd.
 This defines orientation $+D^i_j$ of $E^i_j$.

$-D^i_j$ is defined by reversing the orientation of $D^i_j$.
\end{Definition}

\begin{Remark}
If $G$ is a proper $g$-graph and Pfaffian orientation $D_0$ 
 is fixed, then $D^i_j$ is uniquelly determined for each $ij$.
\end{Remark}


\begin{Definition}
Let $G$ be a proper $g$-graph, $g \geq 1$. An orientation $D$ of $G$
 which equals to $D^i_j$ or $-D^i_j$ on $E^i_j$ and to $D_0$ 
 on $E_0$ is called {\it relevant}. We define its type 
 $r(D) \in \{+1,-1\}^{2g}$ as follows.
For $i =0,\dots,g-1$ and $j =1,2$, $r(D)_{2i + j}$ equals to $+1$ or $-1$
according to the sign of $D^{i+1}_j$ in $D$.
\end{Definition}

\begin{Definition}
Let $G=(V,E)$ be a proper $g$-graph and let $A$ be a subset of its edges. 
 We define its type $t(A) \in \{+1,-1\}^{2g}$
 as follows. For $i =0,..,g-1$ and $j =1,2$, we let $t(A)_{2i + j}$ equal to
 $(-1)^{s(A)_{2i+j}}$, 
 where $s(A)_{2i+j}$ equals to the number of edges of $A$
 which belong to $E^{i+1}_j$.

Let $CR(A)\wug \sum_{i=0}^{g-1} s(A)_{2i+1}\cdot s(A)_{2i+2}$.

Let $BR(A)$ be the subset of edges of $A$ 
which do not belong to $E_0$. 

For each $e\in BR(A)$, let $d(e)=2i+j$ such that $e\in E^{i+1}_j$.
\end{Definition}

\medskip
Let $G$ be a proper $g$-graph. Any alternating cycle with respect 
to $M_0$ will be called {\it alternating cycle}.
If $C$ is a cycle of even length or a cycle embeddedd in the 
plane, then we denote by $l(C)$ the number of arcs of $C$ directed 
clockwise, modulo 2.

We want to show that 
$sgn(D,M_0\Delta P)$ depends only on $t(M_0\Delta P)$ and $r(D)$. 

\begin{Lemma}
\label{sgn0}
Let $G$ be a proper $g$-graph.
Let $C_1,...,C_k$ be vertex-disjoint cycles of $G$ and let ${\cal C}$
denote their union. Then $$CR({\cal C})\wug \sum_{i=1}^k CR(C_i).$$
\end{Lemma}
\medskip\noindent
{\bf Proof.}
$CR({\cal C})$ equals to the sum modulo $2$ of 
$s({\cal C})_{2i+1}\cdot s({\cal C})_{2i+2}$,
 $i=0,...,g-1$.
Now consider the drawing of cycles $C_1,...,C_k$ in the plane,
 obtained by projecting each $E^i_j$ outside of $B_0$. 
 The total number of crossings modulo $2$ 
 also equals to the sum modulo $2$ of 
$s({\cal C})_{2i+1}\cdot s({\cal C})_{2i+2}$,
 $i=0,...,g-1$.
 Each $C_l$, $l=1,...,k$
 becomes a closed curve in the plane.
 Each pair of curves representing $C_i$ and $C_j$ intersect each 
other an even number of times. Hence we can forget these crossings 
without influencing 
the sum modulo $2$ of $s({\cal C})_{2i+1}\cdot s({\cal C})_{2i+2}$,
 $i=0,...,g-1$. Each of the remaining crossings is a crossing 
 of some $C_l$, $l=1,...,k$. 
\done

\medskip


Next we consider the case that there is exactly one alternating cycle
 of $M_0\Delta P$.

\medskip

\begin{Theorem}
\label{sgn1}
Let $G$ be a proper $g$-graph and let $D$ be a relevant orientation of $G$.
Let $C$ be an  alternating cycle of $G$. Then
$$l(C)\wug [|BR(C)|-1-CR(C) + 1/2 \sum_{e\in BR(C)}(r(D)_{d(e)}+1)].$$
\end{Theorem}
\medskip\noindent
{\bf Proof.}
We will assume without loss of generality that $G=C \cup C_0 \cup M_0$.

%An almost alternating cycle $C$ is called {\it simple} 
% if it contains exactly one edge out of $E_0$.
% If $e$ is the edge of $C$ not in $E_0$ then we let $d(C)=d(e)$.
%First we show that \ref{sgn1} holds for simple cycles.

%{\bf Claim~1.}
%If $C$ is a simple cycle of $D$ then $l(C)=1/2(1+r(D)_d)$, where $d=d(C)$.

%{\bf Proof of Claim~1.}
%We need to show that $l(C)=1$ iff $r(D)_d=+1$. If 
% $r(D)_d=+1$ then $C$ is clockwise odd by the definition of the relevant
% orientation. If 
% $r(D)_d=-1$ then $C$ is obtained from a clockwise odd cycle by reversing the
% orientation of exactly one edge, hence $l(C)=0$.

%{\bf End of Claim~1.}


{\bf Claim~1.}
Let for each $i=1,...g$, $C$ intersects at most one of $E^i_1, E^i_2$.
Then $$l(C)\wug [|BR(C)|-1 + 1/2 \sum_{e\in BR(C)}(r(D)_{d(e)}+1)].$$

{\bf Proof of Claim~1.}
$C$ satisfying the properties of Claim~2 may be embedded in a planar way,
 by projecting the non-empty bridges outside of $B_0$.
 Hence $l(C)=1$ iff $|\{e \in BR(C): r(D)_{d(e)}=-1\}|\wug 0$. 
>From this Claim~1 follows.

{\bf End of Claim~1.}

\medskip

We procede by induction on $|BR(C)|$. The case $|BR(C)|=0$ is 
considered in Claim~1.

Let theorem hold for all alternating cycles $C'$
with  $|BR(C)|>|BR(C')|$. Hence for such alternating cycles,
 $l(C')$ depends only on $t(C')$ and $r(D)$. 

 We let $l(t(F),r(H))$ denote the parity of the 
 number of edges oriented clockwise of alternating cycle $F$ with
 $|BR(F)|<|BR(C)|$, in  relevant orientation $H$ of a proper $g$-graph.

We will make the following notational agreement: if a segment $S$ of $C_0$
 is traversed clockwise then we denote it by $+S$, otherwise by $-S$. 

If $P$ is a path together with a prescribed way of traversing it,
 we denote by $l(P)$ the parity of
the number of arcs of $P$ oriented in agreement
 with the way of traversing $P$.
 
\medskip

{\bf Claim~2.}
Let there be a bridge $B=B^i_j$ containing more than one edge of $C$. 
Then \ref{sgn1} holds.

{\bf Proof of Claim~2.}
Let $e,f$ be two edges of $C$ drawn on $B$ which `see' each other on $B$, i.e.
 there is no other edge of $C$ drawn between them on $B$.

We remind that $C_0$ denotes the outer face of $G_0$ and $e,f$ 
do not belong to $M_0\subset E_0$.

Without loss of generality let $e$ be nearer to edge 
$[a_{2(i-1)+j},a_{2(i-1)+j+3}]$ of $B=B^i_j$ than $f$. 

Let $R$ be the cycle of $G$ formed by $e,f$ and two subpaths
$R_1,R_2$ of $C_0$ defined by the endvertices of $e,f$.
By the choice of $e,f$, $R$ is a face of the planar drawing of 
$G^i_j=(V,E_0\cup E^i_j)$. Observe that $l(R)=1$ in the 
orientation of $G^i_j$ induced by the relevant orientation $D$.
 
Let us consider new edge $g$ (not belonging to $G$),
 between endpoints of $e,f$ such that one of two cycles $H_1,H_2$
 formed by $g$ and $C$ and containing $g$  is alternating.
 Without loss of generality, let $g$ use vertex $u \in R_1\cap e$. 
Hence we have that $g=uv_1$ or $g=uv_2$ where $u \in R_1\cap e$ and 
$v_i \in R_i\cap f$, $i=1,2$.

We denote  two opposite orientations of $g$ by $g_1,g_2$. 
Let $H_1$ use $g_1$ and $H_2$ use $g_2$.

Observe that $l(C)=l(H_1)+l(H_2)$.

We will assume without loss of generality that $H_2$ is alternating. 
Hence $H_1$ contains both $e,f$. 

We distinguish two cases now.

{\bf Case~1: $g=uv_1$.}

Let $G'=G\cup \{g_1,g_2\}$. We consider $g_1,g_2$ embedded on
$B_0$ along $R_1$.

 Observe that $CR(C)\wug CR(H_1)+CR(H_2)$:
let us project all the edges of $G'-E_0$ outside of $B_0$.
The edge-crossings are the same as the original edge-crossings of $G$;
hence the parity of the number of edge-crossings of $G'$ equals to 
$CR(C)$.

In addition to these crossings, $H_1$ and $H_2$ share two vertices of
$g_1,g_2$. However, in our plane drawing these two vertices
are touching points between the closed curves
representing $H_1,H_2$, not crossing points. Hence,
by the same argument as in the proof of Lemma \ref{sgn0},
$CR(C)$ equals the sum modulo $2$ of the number of crossings of $H_1$
 and the number of crossings of $H_2$. The number of crossings of
 $H_i$ modulo $2$ equals $CR(H_i)$, $i=1,2$. Hence summarising
$CR(C)\wug CR(H_1)+CR(H_2)$.
 
We construct two digraphs $D_1, D_2$ as follows:

$D_1$ is obtained from $D-\{e,f,\}$ 
by adding new vertices $u',v'_1$ of degree $2$,
incident with new arcs $e',f',g'_1$. $e'f',g'_1$ are obtained from $e,f,g_1$
 by replacing $u$ by $u'$ and $v_1$ by $v'_1$.
 We extend $B_0$ along $R_2$ and
 consider $e',f',g'_1$ embedded on extended $B_0$. Finally we add $g'_1$
 to $M_0$. Let $H'_1$ be the cycle of $D_1$ obtained from $H_1$
 by replacing $e,f,g_1$ by $e',f',g'_1$.
 We have $l(H_1)=l(H'_1)$.

$D_2$ is obtained from $D-\{e,f,\}$ by adding arc $g_2$. 
We again extend $B_0$ along $R_1$ and consider $g_2$ embedded on 
 extended $B_0$. We let $H'_2=H_2$.
 
Hence for $i=1,2$, $D_i$ is orientation of a proper $g$-graph and
$H'_i$ is an alternating cycle of $D_i$. Moreover $|BR(H'_i)|<|BR(C)|$.
We also have that $CR(H_2)\wug CR(H'_2)$ 
and $CR(H_1)\wug CR(H'_1)$.

We remind that $l(R)=1$ in the orientation of $G^i_j$ induced by $D$. 
Hence, exactly one of $g_i$ is oriented 
so that both cycles it makes with $R$ are clockwise odd.
Let it be $g_2$. Then $D_2$ is a relevant orientation and $D_1$ 
becomes relevant after reversing orientation of $g_1$. By the 
induction assumption for $H'_1,H'_2$,  
$l(H'_2)=l(t(H'_2),r(D_2))$ and $l(H'_1)\wug 
l(t(H'_1),r(D_1))+1.$ 
We have that
   
$$l(C)\wug l(H_1)+l(H_2)\wug l(H'_1)+l(H'_2)\wug $$
$$l(t(H'_1),r(D_1))+l(t(H'_2),r(D_2))+1\wug$$

$$[|BR(C)|-2-2-CR(H'_1) -CR(H'_2)+ 1/2 \sum_{h\in 
BR(C)-\{e,f\}}(r(D)_{d(h)}+1)]+1\wug $$
$$[|BR(C)|-1-CR(C)+1/2 \sum_{h\in BR(C)}(r(D)_{d(h)}+1)].$$
{\bf End of Case~1.}

{\bf Case~2: $g=uv_2$.}

Let $G'=G\cup \{g_1,g_2\}$. We consider $g_1,g_2$ embedded on $B$.

Observe that $CR(C)+1\wug CR(H_1)+CR(H_2)$:
let us project all the edges of $G'-E_0$ outside of $B_0$.
The edge-crossings are: the original crossings of $G$; the crossings
of $g_i$ and an edge $h \neq g_{2-i}$: but the total number of these
crossings is even since each such edge $h$ intersects both $g_1,g_2$.

Hence the parity of the number of edge-crossings equals $CR(C)$.

In addition to these crossings, $H_1$ and $H_2$ share two vertices of
$g_1,g_2$. In our plane drawing one of them is a crossing point
and the other one a touching point 
between the closed curves representing $H_1,H_2$.

Hence, by the same argument as in the proof of Lemma~\ref{sgn0},
$CR(C)+1$ equals the sum modulo $2$ of the number of crossings of edges
of $H_1$ and the number of crossings of the edges of $H_2$. 
The number of crossings of $H_i$ modulo $2$ equals to $CR(H_i)$, $i=1,2$. 
Hence summarising $CR(C)+1\wug CR(H_1)+CR(H_2)$.
 
We construct two digraphs $D_1, D_2$ as follows:

$D_1$ is obtained from $D-\{e,f\}$ 
by adding new arc $g'_1$ between $v_1$ and the endvertex $u'$ of $e$
different from $u$. If $l(fg_1e)=1$ then we let $g'_1=(v_1u')$.
If $l(fg_1e)=0$ then $l(eg_1f)=1$ and we let $g'_1=(u',v_1)$.
 
We consider $g'_1$ embedded on $B$.
Let $H'_1$ be obtained from $H_1$ by replacing $f,g_1,e$ by $g'_1$.
We have $l(H_1)=l(H'_1)$.

$D_2$ is obtained from $D-\{e,f\}$ 
by adding arc $g_2$. We consider $g_2$ embedded on bridge $B$.  
We let $H_2=H'_2$.
 
Hence for $i=1,2$, $D_i$ is orientation of a proper $g$-graph and
$H'_i$ is a cycle of $D_i$. Moreover $|BR(H'_i)|<|BR(C)|$.
We also have that $CR(H_2)=CR(H'_2)$ 
and $CR(H_1)=CR(H'_1)$.

We remind that $l(R)=1$ in the orientation of $G^i_j$ induced by 
$D$. Hence exactly one of $g_i$ is oriented so that
both cycles it makes with $R$ are clockwise odd. Let it be $g_2$.
Hence $D_2$ is relevant with $r(D_2)=r(D)$ if and only 
if $r(D)_{2(i-1)+j}=1$, and we have:

$l(H_2)=l(t(H'_2),r(D))$ if and only if $r(D)_{2(i-1)+j}=1$.
Otherwise $l(H_2)\wug l(t(H'_2),r(D))+1$.

We will show that the same holds for $H'_1$: let $R_3$ be the segment
of $C_0$ such that $H=(e,-R_1,-R_3,-R_2)$ is a cycle.
 
We will show that $l(g'_1,-R_3,-R_2)=1$: 
$l(g'_1,-R_3,-R_2)=l(e,g_1,f,-R_3,-R_2)\wug l(f,-R_3)+l(e,g_1,-R_2)$.

If $r(D)_{2(i-1)+j}=1$ then $l(f,-R_3)=1$ and $l(e,g_1,-R_2)=0$
 since $l(e,g_2,-R_2)=1$.

If $r(D)_{2(i-1)+j}=-1$ then $l(f,-R_3)=0$ and $l(e,g_1,-R_2)=1$
 since $l(e,g_2,-R_2)=0$.

Summarising $l(g'_1,-R_3,-R_2)=1$.

Hence $D_1$ is relevant with $r(D_1)=r(D)$ if and only if 
$r(D)_{2(i-1)+j}=1$, and we again have:

$l(H_1)=l(H'_1)=l(t(H'_1),r(D))$ if and only if 
$r(D)_{2(i-1)+j}=1$. 
Otherwise $l(H_1)=l(H'_1)\wug l(t(H'_1),r(D))+1$.
 
Summarising and using the induction assumption of \ref{sgn1}
for $H'_1,H'_2$ we get:
$$l(C)\wug l(H_1)+l(H_2)\wug $$
$$l(t(H'_1),r(D))+l(t(H'_2),r(D))\wug$$
$$[|BR(C)|-2-CR(C)-1 + $$
$$1/2 \sum_{h\in BR(C)-\{e,f\}}(r(D)_{d(h)}+1)+$$
$$1/2 (r(D)_{d(g_2)}+1)+$$
$$1/2 (r(D)_{d(g'_1)}+1)] \wug $$
$$[|BR(C)|-1-CR(C) + 1/2 \sum_{h\in B(C)}(r(D)_{d(h)}+1)].$$

{\bf End of Case~2.}

{\bf End of Claim~2.}

\medskip
{\bf Claim~3.} Let there be $i$ such that $C$ contains
exactly one edge from both $E^i_1$ and $E^i_2$. Then theorem 
\ref{sgn1} holds.

{\bf Proof of Claim~3.} Let $e,f$ be the two edges on bridges 
$E^i_1$ and $E^i_2$, respectively, and let $C_1$
and $C_2$ be two paths such that $C=(C_1, e, C_2, f)$.

The end-vertices of $e,f$ belong to $C_0$. 
Let us assume that along the boundary of $B_0$ from $a_{4(i-1)+1}$ to 
$a_{4i+1}$, the endvertices of $e,f$ appear in the order 
$(v_1,u_1,v_2,u_2)$ where $e=u_1u_2$ and $f=v_1v_2$.

Let $R_1,R_2$ be two
disjoint subpaths of the segment of $C_0$ between
$a_{4(i-1)+1}$ and $a_{4i+1}$, which cover the endvertices of $e,f$.
$R_1,R_2$ contain no other vertex of $G$ incident with an edge out of $E_0$,
by the choice of $i$. 

$R_1,R_2,e,f$ form a cycle $R$, and without loss of generality, 
let  $R=(+R_1,e,-R_2,f)$ where $R_1$ is traversed clockwise, i.e. 
in agreement with the indices of the vertices along $C_0$, and $R_2$ 
is traversed anticlockwise. 
 
Let us consider new adge $g$ (not belonging to $G$),
 between endpoints of $e,f$ such that one of two cycles $I_1,I_2$
 formed by $g$ and $C$ and containing $g$  is alternating.
 Without loss of generality let $g$ use vertex $u_1 \in R_1\cap e$. 
 Hence we have that
 $g=u_1v_1$ or $g=u_1v_2$ where $u_1 \in R_1\cap e$ and $v_i \in R_i\cap f$,
 $i=1,2$.

 We denote  two opposite orientations of $g$ by $g_1,g_2$. 
 Let $I_1$ use $g_1$ and $I_2$ use $g_2$.

 Observe that $l(C)\wug l(I_1)+l(I_2)$.

We will assume without loss of generality that $I_2$ is alternating. 
Hence $I_1$ contains both $e,f$. 

Let $R_3$ denote the segment of $C_0$ between $u_1$ and $v_2$.

Again we distinguish two cases. 
 
\smallskip\noindent
{\bf Case~1: $g=u_1v_1$.}

In this case $g$ forms a cycle with $R_1$.

Let $G'=G\cup \{g_1,g_2\}$. We consider $g_1,g_2$ embedded on
$B_0$ along $R_1$.

 Observe that $CR(C)\wug CR(I_1)+CR(I_2)$:
let us project all the edges of $G'-E_0$ outside of $B_0$.
The edge-crossings are the same as the original edge-crossings of 
$G$.
Hence the parity of the number of edge-crossings equals $CR(C)$. 

In addition to these crossings, $I_1$ and $I_2$ share two vertices of
$g_1,g_2$. However, in our plane drawing these two vertices
are touching points between the closed curves
representing $I_1,I_2$, not crossing points. Hence,
by the same argument as in the proof of Lemma \ref{sgn0},
$CR(C)$ equals the sum modulo $2$ of the number of crossings of $I_1$
and the number of crossings of $I_2$. The number of crossings of
$I_i$ equals to $CR(I_i)$, $i=1,2$. Hence summarising
$CR(C)\wug CR(I_1)+CR(I_2)$.
 
We construct two digraphs $D_1, D_2$ as follows:

$D_1$ is obtained from $D-\{e,f\}$ 
by adding new vertices $u_1',v'_1$ of degree $2$,
incident with new arcs $e',f',g'_1$. $e'f',g'_1$ are obtained from $e,f,g_1$
 by replacing $u_1$ by $u'_1$ and $v_1$ by $v'_1$.
 We extend $B_0$ along $R_2$ and
 consider $e',f',g'_1$ embedded on extended $B_0$.
 Finally we add $g'_1$
 to $M_0$. Let $I'_1$ be the cycle of $D_1$ obtained from $I_1$
 by replacing $e,f,g_1$ by $e',f',g'_1$.
 We have $l(I_1)=l(I'_1)$.

$D_2$ is obtained from $D-\{e,f\}$ 
by adding arc $g_2$. 
We again extend $B_0$ along $R_1$ and consider $g_2$ embedded on 
 extended $B_0$. We let $I'_2=I_2$.
 
Hence for $i=1,2$, $D_i$ is orientation of a proper $g$-graph and
$I'_i$ is an alternating cycle of $D_i$. Moreover $|BR(I'_i)|<|BR(C)|$.
We also have that $CR(I_2)=CR(I'_2)$ 
and $CR(I_1)-1\wug CR(I'_1)$.


Let us assume without loss of generality that $g_2$ is directed so that 
the cycle $l(-R_1,g_2)=1$. Hence $D_2$ is a relevant orientation.

Observe that $D_1$ is  a relevant orientation if and only if
$r(D)_{d(e)}=r(D)_{d(f)}$:

first we prove if $r(D)_{d(e)}=r(D)_{d(f)}=1$ then $D_1$ is 
a relevant orientation. 

In this case we need to show that $l(-R_2,f',g'_1,e')=1$.

We have $l(g_1',f',-R_3)=l(g_1,f,-R_3)\wug l(g_2,f,-R_3)+1=0$ since 
$r(D_{d(f)})=1$ and thus $l(-R_3,g_2,f)=1$. Moreover 
$l(g'_1,f')=l(f',g'_1)$ since it does not
matter which way two consecutive arcs are traversed.
Hence $l(f',g'_1)=l(-R_3)$.

Moreover $l(-R_2,-R_3,e')=l(-R_2,-R_3,e)=1$ since $r(D)_{d(e)}=1$. 
Replacing $f'g'_1$ for $-R_3$ gives what we needed.
 
Analogously, if $r(D)_{d(e)}=r(D)_{d(f)}=-1$ then $l(-R_2,f',g'_1,e')=1$ 
and $D_1$ is a relevant orientation. 

On the other hand, if $r(D)_{d(e)}\ne r(D)_{d(f)}$ then $D_1$ is 
obtained from a relevant orientation by reversing one arc; hence 
$D_1$ is not relevant. 

Summarizing, 
$$l(I_1)+l(I_2)\wug l(I'_1)+l(I'_2)\wug l(t(I'_1),r(D_1))+l(t(I'_2),r(D_2))+$$
$$1/2(r(D)_{d(e)}-1+r(D)_{d(f)}-1).$$

Using the induction assumption of \ref{sgn1} for $I'_1,I'_2$  we get:
$$l(C)\wug l(I_1)+l(I_2)\wug$$
 $$[l(t(I'_1),r(D_1))+l(t(I'_2),r(D_2))+$$
$$1/2(r(D)_{d(e)}-1+r(D)_{d(f)}-1)]\wug$$
$$[|BR(C)|-4-CR(C)+1 + 1/2 \sum_{h\in BR(C)-\{e,f\}}(r(D)_{d(h)}+1)+$$
$$1/2(r(D)_{d(e)}-1+r(D)_{d(f)}-1)]\wug$$
$$[|BR(C)|-1-CR(C) + 1/2 \sum_{h\in BR(C)}(r(D)_{d(h)}+1)].$$

{\bf End of Case~1.}

\smallskip\noindent
{\bf Case~2: $g=uv_2$.}

In this case $g$ forms a cycle with $R_3$.

Let $G'=G\cup \{g_1,g_2\}$. We consider $g_1,g_2$ embedded on
$B_0$ along $R_3$.

Observe that $CR(C)\wug CR(I_1)+CR(I_2)$:
Let us project all the edges of $G'-E_0$ outside of $B_0$.
The edge-crossings are the same as the original crossings of $G$.

 Hence the parity of the number of edge-crossings equals $CR(C)$.

In addition to these crossings, $I_1$ and $I_2$ share two vertices of
 $g_1,g_2$. In the plane drawing both of them 
 are touching points between the closed curves representing $I_1,I_2$.

Hence, by the same argument as in the proof of Lemma \ref{sgn0},
$CR(C)$ equals the sum modulo $2$ of the number of crossings 
of $I_1$ and the number of crossings of $I_2$. The number of crossings of
 $I_i$ equals to $CR(I_i)$, $i=1,2$. Hence summarising
$CR(C)\wug CR(I_1)+CR(I_2)$.
 
We construct two digraphs $D_1, D_2$ as follows:

$D_1$ is obtained from $D-\{e,f\}$ 
by adding new vertices $u_1',v'_2$ of degree $2$,
incident with new arcs $e',f',g'_1$. $e',f',g'_1$ are obtained from $e,f,g_1$
 by replacing $u_1$ by $u_1'$ and $v_2$ by $v'_2$.
 We extend $B_0$ along $+R_1+R_3+R_2$ and
 consider $e',f',g'_1$ embedded on extended $B_0$.
 Finally we add $g'_1$ to $M_0$. Let $I'_1$ be the cycle of $D_1$ 
 obtained from $I_1$ by replacing $e,f,g_1$ by $e',f',g'_1$.
 We have $l(I_1)=l(I'_1)$.

$D_2$ is obtained from $D-\{e,f,\}$ by adding arc $g_2$. 
We again extend $B_0$ along $R_3$ and consider $g_2$ embedded on 
 extended $B_0$. We let $I'_2=I_2$.
 
Hence for $i=1,2$, $D_i$ is orientation of a proper $g$-graph and
$I'_i$ is an alternating cycle of $D_i$. Moreover $|BR(I'_i)|<|BR(C)|$.
We also have that $CR(I_2)=CR(I'_2)$ and $CR(I_1)-1\wug CR(I'_1)$.

Let us assume without loss of generality that $g_2$ is directed so that
 $l(-R_3,g_2)=1$. Hence $D_2$ is a relevant orientation.

Observe that $D_1$ is  a relevant orientation if and only if
$r(D)_{d(e)}=r(D)_{d(f)}$: 

It again suffices to consider the case that $r(D)_{d(e)}=r(D)_{d(f)}=+1$. 

In this case we need to show that  $l(-R_2,-R_3,-R_1,f',g'_1,e')=1$:

We have $l(-R_1,f',g'_1)=0$ since $r(D_{d(f)})=1$ and thus $l(-R_1,f,g_2)=1$.

Moreover $l(-R_2,-R_3,e')=l(-R_2,-R_3,e)=1$ since $r(D)_{d(e)}=+1$. 

Summarising $l(-R_2,-R_3,-R_1,f',g'_1,e')=1$. 

Hence $$l(I_1)+l(I_2)\wug l(I'_1)+l(I'_2)\wug l(t(I'_1),r(D_1))+
l(t(I'_2),r(D_2))+$$
$$1/2(r(D)_{d(e)}-1+r(D)_{d(f)}-1).$$

Using the induction assumption of \ref{sgn1} for $I_1,I_2$  we get:
$$l(C)\wug l(I_1)+l(I_2)\wug $$
 $$l(t(I'_1),r(D_1))+l(t(I'_2),r(D_2))+$$
$$1/2(r(D)_{d(e)}-1+r(D)_{d(f)}-1)\wug$$
$$|BR(C)|-4-CR(C)+1 + 1/2 \sum_{h\in BR(C)-\{e,f\}}(r(D)_{d(h)}+1)+$$
$$1/2(r(D)_{d(e)}-1+r(D)_{d(f)}-1)\wug$$
$$|BR(C)|-1-CR(C) + 1/2 \sum_{h\in BR(C)}(r(D)_{d(h)}+1).$$

{\bf End of Case~2.}

\noindent
{\bf End of Claim~3.}

Theorem follows from Claim~1,~2,~3.
\done

Next we show that the statement of Theorem~\ref{sgn1} holds
for the set of the alternating cycles of $M_0\Delta P$ as well.

\medskip

\begin{Theorem}
\label{sgn2}
Let $G$ be a proper $g$-graph and let $D$ be a relevant orientation
of $G$. Let $P$ be a perfect matching of $G$. Then 
$$sgn(D,M_0\Delta P)=(-1)^q,$$  where

$$q\wug [|BR(M_0\Delta P)|-CR(M_0\Delta P) +$$
$$ 1/2 \sum_{e\in BR(M\Delta P)}(r(D)_{d(e)}+1)].$$
\end{Theorem}
\medskip\noindent
{\bf Proof.} Let $C_1,...,C_k$ be the alternating cycles of $M_0\Delta P$.
We have
$sgn(D,M_0\Delta P)=(-1)^q,$  where $q\wug l(C_1)+...+l(C_k)-k$.

Using Theorem~\ref{sgn1} for $C_1,...,C_k$ it remains to show:

$$CR(M_0\Delta P)\wug \sum_{j=1}^k CR(C_j).$$ 

This is true by Lemma~\ref{sgn0}.

\done

\begin{Corollary}
\label{toro}
Let $G$ be a proper $1$-graph and $D$ a relevant orientation of 
$G$. Let $C$ be an alternating cycle with respect to $M_0$.
Then  
\begin{enumerate}
\item [1.] if $r(D)=(1,1)$ then $sgn(D,C)=1$ iff           
         $t(C)=(1,1)$ or
         $t(C)=(1,-1)$ or  $t(C)=(-1,1)$. 
 
 \item [2.] If $r(D)=(1,-1)$ then $sgn(D,C)=1$ iff   
            $t(C)=(1,1)$ or
            $t(C)=(-1,-1)$ or  $t(C)=(-1,1)$. 
 
 \item [3.] If $r(D)=(-1,1)$ then $sgn(D,C)=1$ iff   
            $t(C)=(1,1)$ or
            $t(C)=(-1,-1)$ or  $t(C)=(1,-1)$. 
 
 \item[4.]  If $r(D)=(-1,-1)$ then $sgn(D,C)=1$ iff   
            $t(C)=(1,1)$.
\end{enumerate}
\end{Corollary}


\begin{Definition}
Let $G$ be a proper $g$-graph. Let $D$ be a relevant orientation of $G$.
Let $r(D)=(r_1,...,r_{2g})$. We let $c(r(D))$ equal to the product
of $c_i$, $i=0,...,g-1$, where $c_i=c(r_{2i+1},r_{2i+2})$ and 
$c(1,1)=c(1,-1)=c(-1,1)=1/2$ and $c(-1,-1)=-1/2$.
\end{Definition}

\medskip
Observe that $c(r(D))=(-1)^n 2^{-g}$, where
$n=|\{i;r_{2i+1}=r_{2i+2}=-1\}|$.

\begin{Corollary}
\label{sgn4}
Let $G$ be a proper $1$-graph. Let $D_1,D_2,D_3,D_4$ be the 
relevant orientations of $G$. Then 

$${\cal P}(G,x)= \sum_{i=1}^4 c(r(D_i)){\cal P}(D_i,M_0).$$

\end{Corollary}

Corollary~\ref{sgn4} holds for all proper $g$-graphs.
In order to deduce it we start with another corollary of 
Theorem~\ref{sgn2}.

\begin{Corollary}
\label{function}
Let $G$ be a proper $g$-graph, $D$ a relevant orientation of 
$G$ and let $P$ be a perfect matching of $G$. Then 
$sgn(D,M_0\Delta P)$ is a function of $r(D)$ and $t(M_0\Delta P)$ only. 
Let us denote this function by $\sigma (r(D),t(M_0\Delta P))$. 
\end{Corollary}

\begin{Lemma} 
\label{sgn22}
Let $r=(r_1,\dots,r_{2g})$ and $t=(t_1,\dots,t_{2g})$ where 
$r_i,t_i\in \{1,-1\}$. Let $r^j=(r_{2j+1},r_{2j+2})$ and 
$t^j=(t_{2j+1},t_{2j+2})$, $j=0,\dots,g-1$. Then  
$$\sigma(r,t)=\prod_{j=0}^{g-1} \sigma(r^j,t^j).$$
\end{Lemma}

{\bf Proof.}
By Corollary~\ref{function}, $\sigma(r,t)=sgn(D,{\cal C})$ where 
$r(D)=r$, $t({\cal C})=t$ and $D$ is a relevant orientation of a 
proper $g$-graph $G$ such that $G=C_0\cup {\cal C}$. ${\cal C}$ 
is a set of vertex-disjoint cycles $C_1,\dots,C_k$ with the 
following properties:
\begin{enumerate}
\item each $C_i$ is alternating with respect to a perfect matching 
      $M_0$ of $G_0$,
\item for each $i,j$ $|E^i_j| \leq 1$, 
\item for each $i$ there is at most one $j$ such 
      that $|C_j \cap (E^i_1 \cup E^i_2)| \geq 1$, 
\item for each $C_j$ there is exactly one $i$ such that $C_j$ intersects 
      $E^i_1\cup E^i_2$.
\end{enumerate}
Hence, $\sigma(r,t)=sgn(D,{\cal C})= \prod_{i=1}^k sgn(D,C_i)=
\prod_{i=1}^k sgn(D^i,C_i)$

where $D^i$ is the restriction of $D$ to $C_0\cup C_i$.
Finally observe that, by Corollary~\ref{toro}, $\sigma(z_1,z_2)=1$ 
if $z_2=(1,1)$. Hence, using Corollary~\ref{function}, we have that 
$\prod_{i=1}^k sgn(D^i,C_i)= \prod_{j=0}^{g-1} \sigma(r^j,t^j)$, 
which we needed to prove.
\done


\begin{Theorem}
\label{pm}
Let $G$ be a proper $g$-graph. Then 

$${\cal P}(G,x)={\cal L}_g(G,x)=\sum _{i=1}^{4^g} c(r(D_i)) {\cal 
P}(D_i,M_0)$$ 

where $D_i$, $i=1,\dots,4^g$, are the relevant orientations of $G$.
\end{Theorem}

\medskip\noindent
{\bf Proof.} Let $P$ be a perfect matching of $G$.
In each ${\cal P}(D_i,M_0)$, $x(P)$ has coefficient
equal to $sgn(D_i,M_0\Delta P)$. By Corollary~\ref{function}, 
$sgn(D_i,M_0\Delta P)=\sigma(r(D_i),t(M_0\Delta P))$. 

Let 
$${\cal K}_g(t(M_0\Delta P)= \sum _{i=1}^{4^g} c(r(D_i))
\sigma(r(D_i),t(M_0\Delta P))$$. 

Theorem follows from the following claim:

\smallskip\noindent
{\bf Claim.} ${\cal K}_g(t(M_0\Delta P))=1$ for each $t(M_0\Delta P)$.

{\bf Proof of Claim.} We proceed by induction on $g$. 

The basis of the induction when $g=1$ is Corollary~\ref{sgn4}.

To prove the induction step we introduce the following notation. 
If $z$ is a vector in $\{1,-1\}^{2g}$ then we let 
$z=(z(0),\dots,z(g-1))$ where $z(i)=(z_{2i+1},z_{2i+2})$.

We call two relevant orientations $D,D'$ of $G$ {\it equivalent} 
if $(r(D)(1),\dots,r(D)(g-1))=(r(D')(1),\dots,r(D')(g-1))$.  
Clearly, the equivalence classes consist of $4$ elements; let 
${\cal R}_1,\dots,{\cal R}_{4^{g-1}}$ be the equivalence classes 
of the relevant orientations of $G$ and let ${\cal 
R}_j=\{D^j_1,D^j_2,D^j_3,D^j_4\}$, $j=1,\dots,4^{g-1}$.

Finally let $r(D^j_i)(k)=r^j_i(k)$, $k=0,\dots,g-1$ and  
$t=t(M_0\Delta P)$. We have that 

$${\cal K}_g(t)=\sum_{j=1}^{4^{g-1}} \sum_{i=1}^4 
  c(r(D^j_i))\sigma(r(D^j_i),t).$$

Now, by Lemma~\ref{sgn22}, this equals to

$$\sum_{j=1}^{4^{g-1}} \sum_{i=1}^4 
c(r^j_i(0))c(r^j_i(1),\dots,r^j_i(g-1))\prod_{k=0}^{g-1} 
\sigma(r^j_i(k),t(k)).$$

By the definition of the equivalence classes, 
$r^j_1(k)=r^j_2(k)=r^j_3(k)=r^j_4(k)$ for $k\ge 1$ and 
$j=1,\dots,4^{g-1}$. 
Hence, we let $r^j_i(k)=r^j(k)$ and write the above summation as:

$$\sum_{j=1}^{4^{g-1}} c(r^j(1),\dots,r^j(g-1))\prod_{k=1}^{g-1}
\sigma(r^j(k),t(k)) \sum_{i=1}^4 c(r^j_i(0))\sigma(r^j_i(0),t(0))$$.

The internal sum equals to 1 for each $j=1,\dots,4^{g-1}$ by the basis 
step of the induction, and 
hence, using Lemma~\ref{sgn22} for the first sum, we can write the 
above summation as

$$\sum_{j=1}^{4^{g-1}} 
c(r^j(1),\dots,r^j(g-1))\sigma((r^j(1),\dots,r^j(g-1)),(t(1),\dots,t(g-1)))
=$$
$${\cal K}_{g-1}(t(1),\dots,t(g-1))=1,$$

by the induction hypothesis for $g-1$. 

\done

\medskip
As a consequence of Theorem~\ref{Kastel} and Theorem~\ref{pm}, we get

\begin{Corollary}
\label{pm1}
Let $G$ be a proper $g$-graph. Then $s(D_i,M_0)=s(D_j,M_0)$  
for each $i,j\in \{1,\dots,4^g\}$ and 

$${\cal P}(G,x)={\cal L}'_g(G,x)=s(D_1,M_0)\sum _{i=1}^{4^g} c(r(D_i)) 
Pf(A(D_i))$$ 

where $D_i$, $i=1,\dots,4^g$, are the relevant orientations of $G$.
\end{Corollary}


\begin{Corollary}
\label{genus}
Let $G$ be a graph embeddable on an orientable surface of genus $g$. 
 Then ${\cal P}(G,x)$ may be expressed as a linear combination of $4^g$ 
 Pfaffians of matrices $A(D)$, where each $D$ is an orientation of $G$. 
\end{Corollary}
\medskip\noindent
{\bf Proof.}
Orientable surface $O_g$ of genus $g$ may be obtained from $S_g$
 as follows: for each bridge $B$, glue together the two segments in 
 which $B$ intersects the boundary of $B_0$, and delete $B$. 

If a graph $G$ is embeddable on an orientable surface $O_g$ 
 of genus $g$, then without loss of generality no vertex belongs to 
 the boundary of $B_0$. Then, splitting the boundaries back to the bridges,
 this gives a drawing of the graph on $S_g$ such that each vertex lies on 
 $B_0$ but some edges may use several bridges.

We construct a graph $G'$ so that we replace each edge $e$ which 
uses $k$ bridges, $k\geq 1$, by a path $P_e$ of edges 
$(e_1,\dots,e_{2k+1})$ and vertices $v_1,\dots,v_{2k}$. 
We let $x'_{e_1}=x_e$ and $x'_{e_i}=1$ for each $i>1$. 
Next we add edges so that the outer face of the planar part is a 
cycle. We let $x'_e=0$ for each such edge $e$. 

Note that $G'$ is a proper $g$-graph and ${\cal P}(G',x')={\cal P}(G,x)$. 

By Theorem~\ref{pm}, ${\cal P}(G',x')$ may be written as a linear combination
 of $4^g$ Pfaffians of $A(D')$, where each $D'$ is a relevant
 orientation of $G'$.

\smallskip\noindent
{\bf Claim.} For each relevant orientation $D'$ of $G'$ there is an 
orientation $D$ of $G$ so that $Pf(A(D'))=Pf(A(D))$ or 
$Pf(A(D'))=-Pf(A(D))$.
 
{\bf Proof of Claim.} We construct $D$ from $D'$ in two steps:
\begin{enumerate}
\item[1.] delete the edges $e$ of $G'-G$ with $x'_e=0$, 
\item[2.] for each edge $e$ of $G$ which was changed
    into a path $P_e$ of odd length in the construction of $G'$,
    orient $e$ in the direction in which an odd number of edges of $P_e$ 
    is directed in $D'$: this is uniquelly determined since $P_e$ has 
    odd length.
\end{enumerate}

If $P$ is a perfect matching of $G$ then there 
is a unique perfect matching $P'$ of $G'$ such that 
$x(P)=x'(P')$.

Observe that $sgn(D,P\Delta Q)=sgn(D',P'\Delta Q')$ for each 
pair of perfect matchings $P,Q$ of $G$. The claim now follows from 
Theorem~\ref{Kastel}. 

{\bf End of Claim.}

This finishes the proof of the Corollary.

\done


\section{Exact Matching, Pfaffian Orientation, and Permanents.}

The results of the previous sections have interesting algorithmic 
consequences. 

\begin{Theorem}
Let $S$ be an orientable surface and $k$ a fixed positive integer.
Let ${\cal G}$ be the class of graphs which may be embedded on $S$ and 
such that the edges are partitioned into at most $k$ classes and variables
$x_e$ are equal in each class. Then
${\cal P}(G,x)$ may be determined efficiently for $G\in {\cal G}$. 
As a consequence, it is possible to verify efficiently whether 
$G\in {\cal G}$ is Pfaffian.
\end{Theorem}

\medskip\noindent
{\bf Proof.} It follows from Theorems~\ref{pm} and \ref{genus} 
that ${\cal P}(G,x)$ may be determined efficiently. 

Concerning the problem of recognizing whether $G$ is Pfaffian,
 we procede as follows: it was proved by Vazirani and Yannakakis 
(see the proof of theorem $3.1$ of \cite{VY}) that there is an orientation
 $D$ of graph $G$ so that $G$ is Pfaffian if and only if $D$ is
 its Pfaffian orientation, and moreover $D$ may be constructed
 efficiently. Hence $Pf(A(D))$ equals to the number of the perfect
 matchings of $G$ if and only if $G$ is Pfaffian, and it means
 that we can decide efficiently whether a graph is Pfaffian once 
 we can compute efficiently its number of perfect matchings.

\done

In particular the following well-known problem may be solved 
efficiently for the graphs embeddable on an arbitrary fixed orientable 
surface:

{\bf Exact Matching Problem.} Given a graph $G$ with some edges 
coloured red, and a number $h$. Find out whether $G$ has a perfect 
matching with exactly $h$ red edges. 

\smallskip
Next we consider permanents of square matrices.

In $1913$, Polya (\cite{Polya}) suggested computing the permanent of a 
matrix $A$ by changing the signs of some entries of $A$ so that the 
determinant of the resulting matrix equals the permanent of $A$.
Let us call a $0,1$-matrix $A$ {\it convertible} if such a change is possible.

Szego (\cite{Szego}) pointed out in the same year that not all matrices 
are convertible.

This may be explained nowadays using a complexity argument. 
There is an efficient algorithm to compute the determinant, while
Valiant proved that the problem of computing the permanent of a $0,1$ 
matrix is $\#P$-complete (see \cite{Val}).

The computational problem of 
recognition of convertible matrices has been proved recently
to admit a polynomial algorithm by McCuaig, Robertson, Seymour and Thomas
(see \cite{RST}). An earlier paper of Galluccio and Loebl
(see \cite{GL5}) contains a related algorithmic result, as well as 
the history of the problem. 

The recognition of convertible matrices
 is equivalent to the problem of recognition of bipartite
 Pfaffian graphs, and to the `Even Cycle Problem': given a directed
 graph, decide whether it contains a directed cycle of even length. 

 Let $A$ be a square matrix. Denote by $G(A)$ the bipartite graph
 whose two bipartition classes are indexed 
by the rows and the columns of $A$, and for each edge $ij$, 
$a_{ij}=x_{ij}$. Then $per(A)={\cal P}(G(A),x)$.

This means that Corollary~\ref{genus} provides a new combinatorial way
 to compute permanents of square matrices: $per(A)$ may be written
 as a linear combination of $4^g$ terms of form $Pf(A(D))$,
 where $D$ is an orientation of $G(A)$ and $g$ is the 
 genus of $G(A)$.

Since $G(A)$ is a bipartite graph, the non-zero entries of  
$A(D)$ belong to two blocks $A_1,A_2$,
 where $A_1$ is obtained from $A$ by
 changing the sign of some entries and $A_2=-A_1$.
 Moreover $|Pf(A(D)|=|det(A_1)|=|det(A_2)|$ by 
 Theorem~\ref{Cayley}.

This means that the method of Polya may be completed as follows:

\begin{Corollary}
Let $A$ be a square matrix. Then $per(A)$ may be expressed
 as a linear combination of terms of form $det(A^i)$, $i=1,...,4^g$,
 where each $A^i$ is obtained from $A$ by changing the sign
 of some entries.
\end{Corollary}

 
\bigskip

{\bf Concluding Remarks.}
In a continuation of this paper which is in preparation
  we consider the following related
 problems: 
\begin{enumerate}
\item[1.] The generating function of $T$-joins and edge-cuts,
\item[2.] The evaluation of Tutte polynomial
          and the weight enumerator of a binary code,
\item[3.] A theory of crystal structures and  
 application of the proposed method to solve the
   Ising problem for three-dimensional crystal structures.
\end{enumerate}

\bigskip
\noindent{\bf Acknowledgements.} The   authors are grateful to 
 Chris Godsil, Robin Thomas and Dominic Welsh for fruitful discussions.

\bibliographystyle{plain}
 
\bibliography{evenbib}

\end{document}


\bibliographystyle{siam}


\begin{thebibliography}{1}

\bibitem{Val}
{\sc L.G. Valiant.}
{\em The Complexity of Computing the Permanent.}
Theor. Comp. Sci. 47, 1986, 85-93.

\bibitem{lp}
{\sc L.~Lov\'asz and M.~Plummer}. {\em Matching Theory}, vol.~29 of {\em Annals of
  Discrete Mathematics}, North-Holland, 1986.



\bibitem{o}
{\sc J.~Oxley}. {\em Matroid Theory}.
Oxford University Press, 1992.

\bibitem{jvw}
{\sc F. Jaeger, D. L. Vertigan, D.J.A. Welsh.}
{\em On the Computational Complexity of Jones and Tutte Polynomials.}
Math. Proc. Camb. Phil. Soc. 108, 1990, 35-53.


\bibitem{w1}
{\sc    D.J.A. Welsh.}
   {\em Matroid Theory}.
   Academic Press, London,  1976.

\bibitem{w2}
{\sc    D.J.A. Welsh.}
   {\em Complexity: Knots, Colourings and Counting}.
   London Mathematical Society Lecture Note Series 186,
   Cambridge University Press 1993.

\bibitem{f}
{\sc M.E. Fisher.}
{\em On the Dimer Solution of Planar Ising Models.}
Journal of Mathematical Physics 7, 10, 1966.

\bibitem{kw}
{\sc M. Kac, J.C. Ward.}
{\em A Combinatorial Solution of the Two-Dimensional Ising Model.}
Physical Review 88, 1952.

\bibitem{pw}
{\sc R.B. Potts, J.C. Ward.}
{\em The Combinatorial Method and the Two-Dimensional Ising Model.}
Progress of Theoretical Physics 13, 1955.

\bibitem{k1}
{\sc P.W. Kasteleyn.}
{\em The Statistics of Dimers on a Lattice.}
Physica 27, 1961.

\bibitem{k2}
{\sc P.W. Kasteleyn.}
{\em The Statistics and Phase Transitions.}
Journal of Mathematical Physics 4, 2  1963.


\bibitem{k3}
{\sc P.W. Kasteleyn.}
{\em Graph Theory and Crystal Physics.}
 Graph Theory and Theoretical Physics, ed. F. Harary
 London, Academic Press 1967, 43-110.

\bibitem{b}
{\sc F. Barahona.}
{\em On the Computational Complexity of Ising Spin Glass Models.}
J. Phys. A 15, 1982.

\bibitem{js}
{\sc M. Jerrum, A. Sinclair.}
{\em Polynomial-Time Approximation Algorithms For the Ising Model.}
SIAM J. Computing 22, 5  1993.

\bibitem{GH}
{\sc O. Goldschmidt, D. S. Hochbaum.}
{\em A Polynomial Algorithm For the $k$-Cut Problem For Fixed $k$.}
Mathematics of Operations Research 19, 1, 1994, 24-37.

\bibitem{DJPSY}
{\sc Dalhaus et.al.}
{\em The Complexity of the Multiway Cuts. Extended Abstract.}
Proc. 1992 ACM Symposium on Theory of Computing, 241-251.


        

\end{thebibliography}


\end{document}







***************************************************************************************************************************************************************88




Next we include two negative results of F. Barahona (see \cite{b}).

A planar rectangular grid will be called {\it $1$-grid},
and in general a rectangular grid with $k$ levels in the third
 coordinate will be called {\it $k$-grid}.
A graph which becomes planar after deleting one vertex is called
 {\it apex graph}.

\medskip

\begin{Theorem}
Let $G$ be a $2$-grid and let $x_e \in \{0,1,-1\}$ for each edge $e$
 of $G$. Then the problem to find the edge-cut of $G$ of
 minimum total weight is an NP-complete problem.
\end{Theorem}

\begin{Theorem}
\label{ap}
The problem to find the maximum size of a cut for the apex graphs
 is NP-complete.
\end{Theorem}

Next we include three results of M. Jerrum and A. Sinclair (see \cite{js}).


\begin{Theorem}
\label{a1}
There exists a fpras (fully polynomial approximation scheme) for 
 ${\cal C}_2(G)$ in any  nonnegative rational vector $(x_e; e\in E(G))$.
\end{Theorem}

\medskip

???? The same result should hold for ${\cal E}(G)$ ?????

\medskip


\begin{Theorem}
\label{a2}
There is no fpras for 
 ${\cal C}_2(G)$ in  $0,1,-1$ vectors $(x_e; e\in E(G))$, even when
 $G$ is a $2$-grid.
\end{Theorem}

\begin{Theorem}
\label{a3}
To determine ${\cal C}_2(G)$ is number $P$ complete even when all non-zero
  $x_e$ equal to  the same positive rational number.
\end{Theorem}

\medskip

The same result as \ref{a3} holds for ${\cal E}(G)$.



\medskip

M. Jerrum and A. Sinclair also proved (see \cite{js}).

\begin{Theorem}
There exists a fpras for ${\cal P}(G)$ when each $x_e$ equals to the same
 non-negative rational number and $G$ is a dense graph.
\end{Theorem}

It is number $P$ complete to determine the number of perfect matchings
 of (bipartite) graphs, i.e. ${\cal P}(G)$ when $x_e=1, e\in E(G)$ 
 (see \cite{Val}). This task for bipartite graphs is equivalent to determining
 permanents of $0,1$ matrices.

It follows from the results of this paper that the number of perfect
 matchings may be determined efficiently for graphs with a bounded
 genus.


 Finally we address the last question:
 May the same result hold for any class of graphs with a forbidden
 minor? The answer to this question is likely to be negative, as the following
 proposition suggests.

\begin{Proposition}
It is NP-complete to determine ${\cal P}(G)$ even when $G$ doesnot
 have a $K_8$ minor, and the variables $x_e; e\in E$ are partitioned into
 two classes.
\end{Proposition}
\medskip\noindent
{\bf Proof.}
It follows from \ref{ap} and \ref{c2} that it is NP-complete to determine
 ${\cal E}(G)$ for apex graphs, even when all the variables
 associated with the edges are equal.
 Applying the construction of Fisher
 to an apex graph, and associating one new
 variable with the new edges,  we get a graph with no $K_8$ minor.
 It follows that to determine ${\cal P}(G)$ is hard for these graphs.

\done

\end{document}

\documentstyle[12pt,fleqn]{article}

%Definizioni Latex Anna 

\newtheorem{Definition}{\bf Definition}[section]
\newtheorem{Example}[Definition]{\bf Example}
\newtheorem{Remark}[Definition]{\bf Remark}
\newtheorem{Lemma}[Definition]{\bf Lemma}
\newtheorem{Theorem}[Definition]{\bf Theorem}
\newtheorem{Corollary}[Definition]{\bf Corollary}
\newtheorem{Proposition}[Definition]{\bf Proposition}

\textwidth 15.6 cm   %**************
\textheight 20 cm  %**************
\oddsidemargin 0.4 cm  %**************
\topmargin 0.6 cm  %**************

\newcommand{\bform}{\begin{displaymath}}
\newcommand{\eform}{\end{displaymath}\smallskip}
\newcommand{\beqn}[1]{\begin{equation}\label{#1}}
\newcommand{\eeqn}{\end{equation}\smallskip}
\newcommand{\beqna}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\eeqna}{\end{eqnarray}\smallskip}
\newcommand{\beqnan}{\begin{eqnarray*}}
\newcommand{\eeqnan}{\end{eqnarray*}\smallskip}
\newcommand{\tr}[1]{#1^{\scriptscriptstyle T}}
\newcommand{\rif}[1]{(\ref{#1})}
\newcommand{\vect}[2]{\left(\begin{array}{c} #1\\#2 \end{array}\right)}
\newcommand{\done}{\hfill$\Box$\par}

\def\Re{I\!\!R}
\def\gt{>}
\def\lt{<}
\def\sp{\;\;}
\def\wug{=^{\!\!\!\!\!^{2}}}
\def\wnug{\ne^{\!\!\!\!\!^{2}}}
\def\prec{<^{\!\!\!\!\!^{L}}}
\def\prece{\le^{\!\!\!\!\!^{L}}}


%Fine Definizioni Latex Anna 

\begin{document}






