Conditions for a graph to be the 1- skeleton of a Surface

Given a connected finite graph G with degree at least 2 at each vertex, what are the conditions G needs to assume in order to attach 2-cells so that the CW- complex is a closed compact surface(2 - manifold).

-
I guess it should be 3-connected, and this is the only condition. (But I might be off by a lot :–)) – Dima Pasechnik Mar 25 '13 at 17:06
There are no conditions at all on a finite graph. Every finite graph is the 1-skeleton of a surface. – Lee Mosher Mar 25 '13 at 17:23
Does "a surface" have an accepted unambiguous definition in this context? – Joseph O'Rourke Mar 25 '13 at 21:22
Every graph embeds in $\mathbb R^3$ so it embeds naturally on the boundary of a regular neighbourhood of any embedding of the graph in $\mathbb R^3$... – Ryan Budney Mar 25 '13 at 21:31
@Ryan -- But the graph might not be the 1-skeleton of the surface -- the regular neighborhood of a cycle is a torus, but the 1-skeleton of a torus can't be a cycle. I wonder whether there's a condition for a graph embedding to be the 1-skeleton of an embedded surface. Not every graph embedding is the 1-skeleton of an embedded surface; for example, we can't attach any 2-cells to a trefoil knot without self-intersection. – Robert Young Mar 26 '13 at 19:04

It suffices to consider a connected graph. Start from a point, which is the 1-skeleton of a sphere. By induction, consider a connected graph $G$ and an edge $E$, and let $S$ be the surface in which the complementary graph $G \setminus E$ is embedded as the 1-skeleton of a CW structure.

If $E$ disconnects $G$ into two connected subgraphs, $S$ has two components and you can embed $G$ in their connected sum. If $E$ is a loop edge with base vertex $v$, you can extend the embedding $G \setminus E \to S$ to an embedding $G \to S$ by including $E$ into a corner of some 2-cell near $v$. If $E$ is a nonloop edge with end vertices $v,w$, but $E$ does not disconnect, there are two cases. If there is just one 2-cell touching $v,w$ then you can embed $E$ into that two cell, connecting one corner to another and cutting that 2-cell into two 2-cells. If there are two or more 2-cells touching $v,w$, then there exist 2-cells $C \ne D$ touching $v,w$ respectively, and you can take the "self-connected sum" of $S$ by taking the connected sum of $C$ and $D$ to form an annulus, and then extend the embedding of $G$ by embedding $E$ in that annulus, cutting from one boundary of the annulus to the opposite and subdividing that annulus into a 2-cell.

-

Choose cyclic orientations of all edges around each vertex and attach discs to the edges following the cyclic orientation around each vertex. The result is an oriented compact surface with a connected component for each connected component of the graph. (Using the convention that an isolated point is glued around the boundary of a disc.)

-
Are you sure that such orientations are well defined when an edge corssing occurs? – Antony Della Vecchia Mar 26 '13 at 18:41
it looks like, you can only attach 2 -cells when these cyclic orientaions are well defined – Antony Della Vecchia Mar 26 '13 at 18:43
There are no edge crossings, the graph is abstract. This construction is the construction of a "fat graph" (or "dessin d'enfant") – Roland Bacher Mar 26 '13 at 19:06

As Lee Mosher says, any graph is the 1-skeleton of an (oriented) surface with boundary. Here's a different proof. Take a generic (in the differential topology sense) map of the graph to the plane. This will be an embedding except for under/over-crossings in the interior of the edges of the graph. Now consider a thickening (2-dimensional neighborhood) of the image of the graph. (Near the crossings, the thickening has two "sheets".) This thickening is a surface with boundary which deformation-retracts onto the graph. If you glue a disk onto each boundary component, the result is a closed surface.

-
Perhaps you also want to cap off the boundaries to define the 2-cells. – Lee Mosher Mar 25 '13 at 19:45
I understood the question as asking for a surface that was cap-off-able, but not capped off. But maybe I misunderstood. I'll edit the answer. – Kevin Walker Mar 25 '13 at 21:13
If I gave you a non planar graph (fairly simple) do you think you can use this construction to tell me what surface(s) it is the 1 skeleton for? – Antony Della Vecchia Mar 26 '13 at 18:36