11
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Marc van Leeuwen
    Commented Oct 3, 2012 at 13:09

4 Answers 4

Reset to default
7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – umar
    Commented Oct 3, 2012 at 9:24
  • $\begingroup$ @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. $\endgroup$
    – Đức Anh
    Commented Oct 3, 2012 at 12:53
  • $\begingroup$ @umar: thank you. I will try to read the text. It seems to be useful. $\endgroup$
    – Đức Anh
    Commented Oct 3, 2012 at 12:54
6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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$ ? $\endgroup$
    – Đức Anh
    Commented Oct 3, 2012 at 12:51
  • 1
    $\begingroup$ $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. $\endgroup$
    – Marc van Leeuwen
    Commented Oct 3, 2012 at 13:02
  • $\begingroup$ Thank you very much. I think I should read more carefully these notions of graph theory. $\endgroup$
    – Đức Anh
    Commented Oct 3, 2012 at 13:15
5
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ are the "faces" still bound by cycles? $\endgroup$
    – Hao S
    Commented May 28, 2018 at 22:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .