Graph Theory – Understanding Faces of a Non-Planar Graph

graph theory

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

Best Answer

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

Related Question