Genus and faces of a graph

Question

I am trying to determine the genus of a simple, undirected, connected graph using Euler's formula.

However, I'm having trouble computing the number of faces of this graph: I seem to be confused about the nature of the casual relationship between face and genus. According to the discussion below,

"faces" of a non-planar graph

the definition of a face is dependent on planarity and spatial embeddings. How, then, can a delineation of the number of yet-defined "faces" be used to determine spatial embeddings? It feels like aporia to me.

If anyone could explain, I would greatly appreciate it.

Answer 1

"Genus" is fundamentally a property of a surface (i.e. two-dimensional manifold). The "genus" of a graph is defined to be the minimum genus over all surfaces in which the graph can be embedded. So you really have to do two things to compute the genus of a graph: demonstrate that it can be embedded in a surface of genus $g$, and that it cannot be embedded into a surface of lower genus. Euler's formula may be of help as you consider putative embeddings into various surfaces, but as you say, an abstract graph doesn't come bundled with an embedding or even a surface, so you can't just "use" Euler's formula to compute the genus.

There are useful results, however. For any genus $g$, the set of graphs (or more properly isomorphism classes of graphs) which can be embedded in a surface of genus $g$ is closed under taking minors, and is therefore characterized by a finite set of excluded minors by the wonderful Graph Minor Theorem. In particular, a graph is planar iff it contains no $K_5$ or $K_{3,3}$ as a minor; such characterizations exist for higher genera as well.

See the wikipedia article on graph minors.