14
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ Later in this paper they give an answer that this is possible. But can anyone give some links to the proof? $\endgroup$
    – user197284
    Commented Sep 14, 2012 at 6:43

1 Answer 1

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – user197284
    Commented Sep 14, 2012 at 20:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Sep 15, 2012 at 6:00
  • $\begingroup$ Yeah, forgot about those cases, sure they have to hold also. Thank you very much! $\endgroup$
    – user197284
    Commented Sep 15, 2012 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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