Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
1  
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
1  
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
1  
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
1  
@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

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer

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.)

share|improve this answer
    
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
1  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.