Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks in advance,

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

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

3 Answers 3

up vote 3 down vote accepted

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.

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

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.

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

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

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

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.