We generalize MacLane's theorem, which characterizes planarity
in terms of generating sets for the cycle space of a graph, to
embeddability criteria for graphs in arbitrary closed surfaces.
Our approach is motivated by homology. We show that a graph can
be embedded in a surface of Euler genus g (orientable or not)
if and only if its has a "sparse" family of closed walks
that generates in the cycle space a subspace
of codimension at most g. A more refined version of this theorem
distinguishes between embeddability in orientable or non-orientable
surfaces of the same Euler genus, thus providing a characterization of
embeddability in any given surface.
Download (short version; extended version)