  We define a multivariate polynomial that generalizes several interlace
polynomials defined by Arratia, Bollobas and Sorkin on the one hand, and Aigner
and van der Holst on the other. We follow the route traced by Sokal, who
defined a multivariate generalization of Tutte's polynomial. We also show that
bounded portions of our interlace polynomial can be evaluated in polynomial
time for graphs of bounded clique-width. Its full evaluation is necessarly
exponential just because of the size of the result.
