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 2cells so that the CW complex is a closed compact surface(2  manifold).

1$\begingroup$ I guess it should be 3connected, and this is the only condition. (But I might be off by a lot :–)) $\endgroup$ – Dima Pasechnik Mar 25 '13 at 17:06

1$\begingroup$ There are no conditions at all on a finite graph. Every finite graph is the 1skeleton of a surface. $\endgroup$ – Lee Mosher Mar 25 '13 at 17:23

1$\begingroup$ Does "a surface" have an accepted unambiguous definition in this context? $\endgroup$ – Joseph O'Rourke Mar 25 '13 at 21:22

$\begingroup$ 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$... $\endgroup$ – Ryan Budney Mar 25 '13 at 21:31

1$\begingroup$ @Ryan  But the graph might not be the 1skeleton of the surface  the regular neighborhood of a cycle is a torus, but the 1skeleton of a torus can't be a cycle. I wonder whether there's a condition for a graph embedding to be the 1skeleton of an embedded surface. Not every graph embedding is the 1skeleton of an embedded surface; for example, we can't attach any 2cells to a trefoil knot without selfintersection. $\endgroup$ – Robert Young Mar 26 '13 at 19:04
It suffices to consider a connected graph. Start from a point, which is the 1skeleton 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 1skeleton 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 2cell 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 2cell touching $v,w$ then you can embed $E$ into that two cell, connecting one corner to another and cutting that 2cell into two 2cells. If there are two or more 2cells touching $v,w$, then there exist 2cells $C \ne D$ touching $v,w$ respectively, and you can take the "selfconnected 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 2cell.
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.)

$\begingroup$ Are you sure that such orientations are well defined when an edge corssing occurs? $\endgroup$ – Antony Della Vecchia Mar 26 '13 at 18:41

$\begingroup$ it looks like, you can only attach 2 cells when these cyclic orientaions are well defined $\endgroup$ – Antony Della Vecchia Mar 26 '13 at 18:43

1$\begingroup$ There are no edge crossings, the graph is abstract. This construction is the construction of a "fat graph" (or "dessin d'enfant") $\endgroup$ – Roland Bacher Mar 26 '13 at 19:06
As Lee Mosher says, any graph is the 1skeleton 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/overcrossings in the interior of the edges of the graph. Now consider a thickening (2dimensional neighborhood) of the image of the graph. (Near the crossings, the thickening has two "sheets".) This thickening is a surface with boundary which deformationretracts onto the graph. If you glue a disk onto each boundary component, the result is a closed surface.

$\begingroup$ Perhaps you also want to cap off the boundaries to define the 2cells. $\endgroup$ – Lee Mosher Mar 25 '13 at 19:45

$\begingroup$ I understood the question as asking for a surface that was capoffable, but not capped off. But maybe I misunderstood. I'll edit the answer. $\endgroup$ – Kevin Walker Mar 25 '13 at 21:13

$\begingroup$ 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? $\endgroup$ – Antony Della Vecchia Mar 26 '13 at 18:36