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

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

-

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

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 then 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

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

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

-

– 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 28, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9502159953117371, "perplexity_flag": "head"}