A-infinity structure on the ribbon graph complex and more general graph complexes Moduli spaces of curves (with nonempty boundary or at least one marked point) admit cell decompositions in which the cells are labelled by ribbon graphs.  In fact, the moduli space of normalised metric ribbon graphs with $n$ boundary components is homeomorphic to the product of the moduli space of curves and an $(n-1)$-simplex.  
From this geometric statement one can show that the ribbon graph complex (a chain complex spanned by ribbon graphs, with the differential given by summing over all edge contractions) computes the cohomology of moduli spaces of curves.
My question is: does anyone know how to describe the cochain level cup product structure on the ribbon graph complex?  By general machinery, if a complex computes the cohomology of a space then it carries an $A_\infty$ structure for which it is equivalent to the cochains on the space with their usual $A_\infty$ structure.
I would like to know if there is a way to write down a combinatorial formula for this $A_\infty$ structure on the ribbon graph complex.
Similarly, the Lie graph complex (in which vertices are labelled by words in a generic Lie algebra) computes the cohomology of the spaces $BOut(F_n)$ (the classifying spaces of outer automorphism groups of free groups).  Is there a way to describe the resulting $A_\infty$ structure on the Lie graph complex?
 A: There is a way to obtain these kinds of spaces as geometric realizations of categories of graphs. See Igusa's book on Reidemeister torison. This gives a simplicial model. Basically its the barycentric subdivision. There is a standard formula for the cup product in this context which will probably work.
A: This is basically an expansion on Ben Cooper's answer.
As far as I know (I'm very happy for anyone to correct me...) this is what's known so far:

*

*In Graph cohomology and Kontsevich cycles, Igusa introduces a certain category $Fat$. The objects of this category are ribbon graphs and the morphisms are edge contraction. He then proves (Theorem 1.22) that there is a rational equivalence
$$ \phi : C_*(Fat) \to \mathcal{G}_* $$
between the chain complex of the nerve of $Fat$ and the ribbon graph complex. Now, like any simplicial complex, there is a canonical diagonal on $C_*(Fat)$, namely the Alexander-Whitney diagonal which gives a description of the cup product.

*It is well-known that $\mathcal{G}_*$ with rational coefficients computes $H_*(\mathcal{M};\mathbb{Q})$ where
$$\mathcal{M} := \coprod \mathcal{M}_{g,n}$$
the union of moduli spaces of smooth Riemann surfaces of genus $g$ and $n$ unlabeled boundary components.

*Given a cyclic $A_\infty$-algebra, with finite dimensional cohomology, inner product is even and symmetric, Kontsevich shows in Feynman diagrams and low-dimensional topology how to associate to it a ''characteristic cocycle" $c_A$ in the graph complex (hence a characteristic class in $H_*(\mathcal{M};\mathbb{Q})$ as well). A good review of this construction is
Charcteristic classes of $A_\infty$-algebras by Lazarev and Hamilton.

*Since there is such a strong connection between the moduli of curves and the $A_\infty$-operad (see e.g. Are there graph models for other moduli spaces?), we might try and look into diagonals in the latter. In the context of $A_\infty$-algebras there are (at least?) 3 different constructions of diagonals: Saneblidze and Umble, Markl and Shnider, and Loday. Maybe there are homotopic but (as far as I know?) nobody proved that. They are also quite painful to work with directly.

*However, in the context of cyclic $A_\infty$-algebras, the situation is different. Lino Amorim and Junwu Tu proved in Tensor products of cyclic $A_\infty$-algebras and their Kontsevich cycles that there is a unique diagonal up to cyclic homotopy. Their diagonal and the Alexander-Whitney diagonal from 1. are homotopic (thus providing an explicit formula as you requested). This diagonal has an explicit combinatorical description, which allows you to write it (at least the initial terms), but it is a very complicated formula.

