“faces” of a non-planar graph

Good afternoon,

I have a question concerning concepts in graph theory. Graph theory is a field quite strange to my knowledge, so my question is maybe stupid.

For a planar graph, we can define its faces as follows : we delete all its edges and its vertices from the plane. Then the remaining part of the plane is a collection of pieces (connected components). Each such piece is called a face.

So how to define faces of a non-planar graph? I would like to know if we can define it from the intuitive figure of a graph.

Duc Anh

EDIT : I would like to explain more where my question comes from. In this slide http://www.aimath.org/~hogben/Goins.pdf, the author writes $K_{3,3}$ has $6$ vertices, $9$ edges and $3$ faces, so I wonder how these faces are defined? Or we only can define them after embedding the graph into some surface of genus $g$?

-
The author of these slides seems to have made some mistake; the set $F$ is clearly nowhere defined, and I have no idea where the values for $f$ come from. – Marc van Leeuwen Oct 3 '12 at 13:09

There is no reasonable definition of faces for an arbitrary graph. Even for a planar graph the definition of faces assumes that in addition to the (abstract) graph a concrete embedding in the plane is given. For instance take a graph constructed starting form two vertices $A,B$ by linking them with simple paths of lengths $1,3,2,3$ (introducing the necessary $5$ intermediate vertices). This graph is certainly planar, but does it contain a triangular face? That depends on how those paths are embedded in the plane (the order given suggests an embedding that does not give rise to a triangular face, but it there does exist an embedding of this graph with a triangular face. For more general graphs you could arrange that any cycle in the graph defines a face for some embedding in a sufficiently complicated surface.

-
Thank you. But I don't understand well your example. I should have assumed that a graph is an ordered pair $(V,E)$ with $V$ a set and $E$ an binairy irreflexive relation on $V$ : for two arbitrary vertices, there is at most one edge joining these vertices. Moreover, if we can not define a face for a planar graph, so how could we understand the theorem of Euler : $v - e + f = 2$ ? – Đức Anh Oct 3 '12 at 12:51
$V=\{A,B,0,1,2,3,4\}$, $E=\{\{A,B\},\{A,0\},\{0,1\},\{1,B\},\{A,2\},\{2,B\},\{A,3\},\{3,4\},\{4,B\}\}$. As for the theorem of Euler, it is about embedded planar graphs. A graph is planar iff it admits an embedding, but the graph itself does not choose one. – Marc van Leeuwen Oct 3 '12 at 13:02
Thank you very much. I think I should read more carefully these notions of graph theory. – Đức Anh Oct 3 '12 at 13:15

Maybe this is something you want: Any graph $G$ can be embedded in a compact surface $S_g$ of genus $g$, for some $g$. The minimum of such $g$ is called the genus of $G$. Then faces of a non-planar graph may be defined as the regions of the embedding of $G$ in the $S_g$.

-
For an explanation of the Genus, you can also take a look at personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/… . Is a genus the same intuitively as putting a vertex at each crossing, thus making the graph planar with more vertices. The minimum number of vertices needed to be put is the genus of G , is that correct? – umar Oct 3 '12 at 9:24
@Paul : Thank you. In fact, I know this fact. I just wonder if we can determine the number of faces of a graph from its intuitive figure on a paper. I have editted my question, you can see the link there. – Đức Anh Oct 3 '12 at 12:53
@umar: thank you. I will try to read the text. It seems to be useful. – Đức Anh Oct 3 '12 at 12:54

In general, the answer to your question is no---from an abstract representation $G=(V,E)$ of a graph, you cannot immediately get any information about its faces in an embedding into a surface. All is not lost, though: You might want to look at rotations. In simple terms, if for each vertex $v$ of $G$ you define an order in which all of the edges adjacent to $v$ would be visited in a rotation about $v$, these orders will determine an embedding of $G$ in some orientable surface: selecting different orders for rotations will give you different embeddings.

-
Thank you very much. Your answer is very clear for me. – Đức Anh Oct 3 '12 at 16:42

For a planar graph, we can define its faces as follows: we delete all its edges and its vertices from the plane. Then the remaining part of the plane is a collection of pieces (connected components). Each such piece is called a face.

It is similar to planar.

A face of the embedded graph is an arcwise connected component of the surface minus the graph.

For example, the torus is up and down connected, left and right connected.

So $K_{3,3}$ has 3 faces on the torus.

-