  We propose a generalization of the concept of a Ribbon graph suitable to
provide combinatorial models for marked surfaces equipped with a G-structure.
Our main insight is that the necessary combinatorics is neatly captured in the
concept of a crossed simplicial group as introduced, independently, by
Krasauskas and Fiedorowicz-Loday. In this context, Connes' cyclic category
leads to Ribbon graphs while other crossed simplicial groups naturally yield
different notions of structured graphs which model unoriented, N-spin, framed,
etc, surfaces. Our main result is that structured graphs provide orbicell
decompositions of the respective G-structured moduli spaces. As an application,
we show how, building on our theory of 2-Segal spaces, the resulting theory can
be used to construct categorified state sum invariants of G-structured
surfaces.
