  We introduce and study wheeled PROPs, an extension of the theory of PROPs
which can treat traces and, in particular, solutions to the master equations
which involve divergence operators. We construct a dg free wheeled PROP whose
representations are in one-to-one correspondence with formal germs of
SP-manifolds, key geometric objects in the theory of Batalin-Vilkovisky
quantization. We also construct minimal wheeled resolutions of classical
operads Com and Ass as rather non-obvious extensions of Com_infty and
Ass_infty, involving, e.g., a mysterious mixture of associahedra with
cyclohedra. Finally, we apply the above results to a computation of cohomology
of a directed version of Kontsevich's complex of ribbon graphs.
