<p>This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along the graph edges. A well known theorem in topology (called the classification of 2-manifolds) tells us exactly which 2-manifolds are possible, and they are all distinguishable from each other either by whether they are orientable or whether they have the same Euler characteristic (or both) — see <a href="http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdf">http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdf</a> for some reasonable lecture notes on this subject, that include the proof you're asking for. There are no other 2-manifolds in this classification that have the same Euler characteristic as the sphere, so if you calculate the Euler characteristic and find that it matches the formula for a sphere, you know your embedding must be onto a sphere.</p>

<p>Finding an embedding with actual geometric coordinates in the plane, once you have a planar combinatorial embedding, is not entirely trivial but can be done e.g. using the theory of Schnyder woods. I have some lecture notes on this at <a href="http://www.ics.uci.edu/~eppstein/gina/schnyder/">http://www.ics.uci.edu/~eppstein/gina/schnyder/</a> for instance.</p>

CC BY-SA 3.0
2012-09-14T20:48:17.447Z
Thank you very much for such an extensive answer! I've read the first paper and it seems that I understood the proof. But I have one question left: does this all mean that if we will define surfaces whatever we like (I mean some arbitrary subset of edges, not like in combinatorial embedding with counterclockwise order and stuff), glue them all together in such a way that glue is only on sharing edges of 2 surfaces, define resulting 'knots' at the endpoints of edges as vertices AND if Euler's formula holds, this is a planar graph?
user197284
CC BY-SA 3.0
2012-09-15T06:00:00.293Z
You have to be careful that you get a manifold: the faces of the embedding should be topological disks, you're not allowed to leave unglued edges, each edge should only be glued to one other edge, and at each vertex there should be only one cycle of edges and faces glued around it (not like what you get if you glue two cones together at their tips). Also you need to either start with a connected graph, or count the Euler characteristic for each component separately. But if all that is true, and Euler's formula holds, then yes, it's planar.
David Eppstein
CC BY-SA 3.0
2012-09-15T06:40:16.937Z
Yeah, forgot about those cases, sure they have to hold also. Thank you very much!
user197284
CC BY-SA 3.0
2012-09-14T07:13:35.190Z
2012-09-14T07:13:35.190Z
David Eppstein
<p>Here : <a href="http://www.planarity.org/Klein_elementary_graph_theory.pdf">http://www.planarity.org/Klein_elementary_graph_theory.pdf</a> (in chapter embeddings) is given definition of <em>combinatorial embedding</em> of a planar graph. (with definition of faces and so on) Though it could be easily used for any graph, they define planar graph as the graph, for which Euler formula holds (assuming that graph is connected). It pretty much understandable that for every <strong>plane</strong> graph the definition of faces in combinatorial embedding is similar to the definition of faces in topological embedding. (assuming that graph is connected. Otherwise in combinatorial embedding we'll have infinite face for every connected component)</p>

<p>The question is: if for some connected graph it's combinatorial embedding satisfies Euler formula, does this mean that this graph is planar in topological sense (it has plane embedding, i.e. it's <strong>plane</strong> graph)?</p>

CC BY-SA 3.0
2012-09-14T06:43:13.220Z
Later in this paper they give an answer that this is possible. But can anyone give some links to the proof?
user197284
<graph-theory><co.combinatorics><planar-graphs>
Combinatorial embedding of a graph
user197284
# Combinatorial embedding of a graph

(Asked by: username_0 on 2012-09-14)

Here : <http://www.planarity.org/Klein_elementary_graph_theory.pdf> (in chapter embeddings) is given definition of *combinatorial embedding* of a planar graph. (with definition of faces and so on) Though it could be easily used for any graph, they define planar graph as the graph, for which Euler formula holds (assuming that graph is connected). It pretty much understandable that for every **plane** graph the definition of faces in combinatorial embedding is similar to the definition of faces in topological embedding. (assuming that graph is connected. Otherwise in combinatorial embedding we'll have infinite face for every connected component)

The question is: if for some connected graph it's combinatorial embedding satisfies Euler formula, does this mean that this graph is planar in topological sense (it has plane embedding, i.e. it's **plane** graph)?

**Tags:** graph-theory, co.combinatorics, planar-graphs

> **Comments:**
> **username_0**: Later in this paper they give an answer that this is possible. But can anyone give some links to the proof?  

---

## 1 answers

### Answer by username_1 on 2012-09-14. Score: 17 | Accepted answer

This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along the graph edges. A well known theorem in topology (called the classification of 2-manifolds) tells us exactly which 2-manifolds are possible, and they are all distinguishable from each other either by whether they are orientable or whether they have the same Euler characteristic (or both) — see <http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdf> for some reasonable lecture notes on this subject, that include the proof you're asking for. There are no other 2-manifolds in this classification that have the same Euler characteristic as the sphere, so if you calculate the Euler characteristic and find that it matches the formula for a sphere, you know your embedding must be onto a sphere.

Finding an embedding with actual geometric coordinates in the plane, once you have a planar combinatorial embedding, is not entirely trivial but can be done e.g. using the theory of Schnyder woods. I have some lecture notes on this at <http://www.ics.uci.edu/~eppstein/gina/schnyder/> for instance.

> **Comments:**
> **username_0**: Thank you very much for such an extensive answer! I've read the first paper and it seems that I understood the proof. But I have one question left: does this all mean that if we will define surfaces whatever we like (I mean some arbitrary subset of edges, not like in combinatorial embedding with counterclockwise order and stuff), glue them all together in such a way that glue is only on sharing edges of 2 surfaces, define resulting 'knots' at the endpoints of edges as vertices AND if Euler's formula holds, this is a planar graph?  
> **username_1**: You have to be careful that you get a manifold: the faces of the embedding should be topological disks, you're not allowed to leave unglued edges, each edge should only be glued to one other edge, and at each vertex there should be only one cycle of edges and faces glued around it (not like what you get if you glue two cones together at their tips). Also you need to either start with a connected graph, or count the Euler characteristic for each component separately. But if all that is true, and Euler's formula holds, then yes, it's planar.  
> **username_0**: Yeah, forgot about those cases, sure they have to hold also. Thank you very much!  

---

