Is it possible to define or calculate the number of faces in a non-planar graph? If so, under what conditions or transformations (such as embedding into a higher genus surface) can the concept of a face be extended to non-planar graphs, and how does it relate to Euler's formula or its generalizations?
You can always embed a graph into a surface with sufficiently high genus such that each face is homeomorphic to a cell. Then Euler's formula generalises to V-E+F = chi, the Euler characteristic of the surface, which is given by 2-2g for orientable surfaces with genus g and 2-g for non-orientable surfaces :)
Technically what you need to qualify as a face in a higher genus surface is a 2-cell (or cellular) embedding, so that no face has a hole.
A good reference for this kind of question is the book
G.Ringel: Map color theorem, Springer 1974.
Chapter 4 is about Graphs on surfaces, which is the topic of your question.
However, this old book does not answer it completely.
Among others there is the following theorem 4.3 and 4.4 combined:
Let G be a graph, all of whose vertices have valence >= 2.
G can be triangularly embedded into the surface S (i.e. there exists a polyhedron F on S such that G is isomorphic to the 1-skeleton of F and all faces of F are triangles) if and only if a1=3(a0-E(S)) holds.
(Here a0 is the number of vertices and a1 the number of edges of G,
while E(S) is the Euler characteristic of S.)
Note that the equality above is a
- Badges
- Science topic