MacLane's theorem for arbitrary surfaces

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)