  We introduce a new graph polynomial in two variables. This ``interlace''
polynomial can be computed in two very different ways. The first is an
expansion analogous to the state space expansion of the Tutte polynomial; the
significant differences are that our expansion is over vertex rather than edge
subsets, and the rank and nullity employed are those of an adjacency matrix
rather than an incidence matrix.
  The second computation is by a three-term reduction formula involving a graph
pivot; the pivot arose previously in the study of interlacement and Euler
circuits in four-regular graphs.
  We consider a few properties and specializations of the two-variable
interlace polynomial. One specialization, the ``vertex-nullity interlace
polynomial'', is the single-variable interlace graph polynomial we studied
previously, closely related to the Tutte-Martin polynomial on isotropic systems
previously considered by Bouchet. Another, the ``vertex-rank interlace
polynomial'', is equally interesting. Yet another specialization of the
two-variable polynomial is the independent-set polynomial.
