\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
{\bf Anna Galluccio and Martin Loebl}
\medskip
\noindent
{\bf On the Theory of Pfaffian Orientations.
\noindent II. $T$-joins, $k$-cuts, and Duality of Enumeration.}
\vskip.5cm
This is a continuation of our paper ``A Theory of Pfaffian Orientations I:
Perfect Matchings and Permanents".
We present a new combinatorial way to compute the generating
functions of $T$-joins and $k$-cuts of graphs.
As a consequence, we show that the computational problem
to find the maximum weight of an edge-cut is polynomially
solvable for the instances $(G,w)$ where $G$ is a graph
embedded on an arbitrary
fixed orientable surface and the weight function $w$
has only a bounded number
of different values. We also survey the
related results concerning a duality of the Tutte polynomial, and present
an application for the weight enumerator of a binary code.
In a continuation of this paper which is in preparation
we present an application
to the Ising problem of three-dimensional crystal structures.
\bye