Genus Measures the Least Surface Complexity
A graph may fail to have a crossing-free drawing in the plane but still have one on a more complicated surface. Genus measures how complicated a surface must be before such a drawing is possible. The key word is least: a graph’s genus is not the complexity of a surface on which it happens to be drawn, but the minimum complexity among all surfaces that allow an embedding.
All graphs in this tutorial are finite and simple. An embedding of a graph in a surface places each vertex at a distinct point and each edge along an arc between its endpoints, with no two edge-arcs meeting except at a common endpoint. The surface is a closed surface: it is compact, connected and has no boundary. An embedding need not be cellular. It is cellular when every component of the complement of the embedded graph is an open disk.
The closed connected orientable surfaces are the sphere with \(g\) handles, where \(g\) is a nonnegative integer. The sphere has \(g=0\), and the torus has \(g=1\). The nonorientable surfaces are the projective plane with additional crosscaps: denote the surface with \(k\) crosscaps by \(N_k\), for \(k\geq 1\). These surfaces cannot be given a consistent global orientation.
In this convention, planar graphs have nonorientable genus \(0\), not \(1\). The sphere is included as the zero-complexity case, even though it is orientable rather than nonorientable. Another convention considers only the surfaces \(N_k\) with \(k\geq1\); under that convention a planar graph can be embedded in the projective plane, so its least such \(k\) is \(1\). Always check which convention is in use.
The least values in these definitions exist. A finite graph can be drawn in the plane with finitely many crossings; replacing small neighborhoods of crossings by suitable surface patches gives an embedding on a surface of sufficiently high complexity. The genus parameters then select the least eligible integer. No claim that an arbitrary embedding is cellular is part of either definition.
What the Two Parameters Compare
Orientable genus counts handles in the least orientable surface that supports an embedding. Nonorientable genus counts crosscaps in the least nonorientable surface, with the stated zero convention for planar graphs. They are separate measurements, not two names for a single number. In particular, the definitions do not imply that one can be obtained from the other by simply replacing a handle with one crosscap.
Both parameters are zero exactly when the graph is planar, where “planar” means that the graph has an embedding in the sphere (equivalently, a crossing-free drawing in the plane). For the orientable parameter this follows because the genus-zero orientable surface is the sphere. For the nonorientable parameter it is exactly the zero convention in the definition.
Proof. Let \(S\) be an orientable surface of genus \(\gamma(G)\) in which \(G\) has an embedding. Delete from this embedding the arcs for edges of \(G\) that are not in \(H\), and delete the points for vertices not in \(H\), together with any incident edge-arcs that were deleted with them. The remaining points and arcs give an embedding of \(H\) in the same surface. Therefore \(\gamma(H)\), the least orientable genus allowing an embedding of \(H\), is at most \(\gamma(G)\). The same restriction argument applies to an embedding in a surface attaining \(\widetilde{\gamma}(G)\). If that surface is the sphere, \(H\) embeds in the sphere and has nonorientable genus \(0\); otherwise \(H\) embeds in the same \(N_k\), so its nonorientable genus is at most \(k\). Thus \(\widetilde{\gamma}(H)\leq\widetilde{\gamma}(G)\) as well. This also covers the graph with no vertices, since it embeds in the sphere and has both parameters zero. \(\square\)
This monotonicity gives a useful test: if a graph contains a subgraph whose genus is known, the larger graph’s genus cannot be smaller. It does not, by itself, determine the genus of the larger graph. A subgraph may require a more complicated surface than the remaining graph would require on its own, while extra edges can also impose further constraints.
Worked Examples from Explicit Embeddings
Worked Example: A Tree
Let \(T\) be the graph with \(V(T)=\{1,2,3,4,5\}\) and \(E(T)=\{12,23,24,45\}\). We determine both genus parameters.
Embed vertex \(2\) as a point in the plane, and place \(1,3,4\) at distinct nearby points. Draw the three edges \(12,23,24\) as nonintersecting arcs from \(2\). Place \(5\) near \(4\) and draw \(45\) without meeting any other edge. This gives a plane embedding, hence a sphere embedding. Therefore \(\gamma(T)=0\) and \(\widetilde{\gamma}(T)=0\), since neither parameter can be negative.
Check: the listed edges connect \(1\) to \(2\), \(3\) to \(2\), \(4\) to \(2\), and \(5\) to \(4\); the described drawing includes every edge and introduces no crossing. Thus it is an embedding of precisely the given graph, not merely of a graph with the same vertices.
Worked Example: The Complete Graph \(K_4\)
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Draw a triangle with vertices \(1,2,3\), and place vertex \(4\) inside it. Draw \(14,24,34\) from the inside point to the three triangle vertices, with the arcs meeting only at \(4\).
The three sides \(12,23,31\) and the three arcs from \(4\) are exactly the six listed edges. The drawing has no crossings, so \(G\) embeds in the sphere. Consequently, \(\gamma(G)=0\) and \(\widetilde{\gamma}(G)=0\). In fact, this embedding is cellular: its complementary regions are the three triangular regions inside the outer triangle and the region outside it, which is also a disk on the sphere.
Check: the edge count from the list is \(3+3=6\): three edges among \(\{1,2,3\}\) and three incident with \(4\). The drawing contains those same six edges, so no edge is missing or added.
Worked Example: The Complete Bipartite Graph \(K_{2,3}\)
Let \(G=K_{2,3}\) have parts \(\{a,b\}\) and \(\{x,y,z\}\). Thus \(V(G)=\{a,b,x,y,z\}\) and \(E(G)=\{ax,bx,ay,by,az,bz\}\); there are no edges within either part.
Draw three paths from \(a\) to \(b\): the length-two paths \(a,x,b\), \(a,y,b\), and \(a,z,b\). Place these paths side by side in the plane, with their interiors disjoint. Their endpoints \(a\) and \(b\) are the only shared vertices. The six path edges are exactly the six edges in \(E(G)\), so this is a plane embedding.
It follows that \(\gamma(G)=0\) and \(\widetilde{\gamma}(G)=0\). This example also illustrates why a graph’s specified vertex partition does not have to be drawn as two separated regions: what matters is that the edges can be drawn without crossings.
Check: each of \(x,y,z\) is joined to both \(a\) and \(b\), giving \(2+2+2=6\) edges. The three paths use two edges each, also giving \(3\cdot2=6\), and their interiors are disjoint by construction.
A Particular Surface Is Not the Genus
Even a simple graph can be embedded on a surface more complicated than the one that determines its genus. For example, place a plane embedding of a cycle inside a disk on the torus. This is an embedding in a genus-one surface, but the same cycle already embeds in the sphere, so both of its genus parameters are zero. The torus drawing does not show that the graph has genus one.
This distinction also matters when using Euler’s formula on surfaces. The cellular form relates the numbers of vertices, edges and faces to the Euler characteristic of the surface, but it requires a cellular embedding. Counting components of the complement is not enough: a complementary region need not be an open disk.
Common mistake. Consider \(C_3\), with \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\), drawn as a small triangle inside a disk on a torus. One might count two components of the complement—the inside and outside of the triangle—and then write \(3-3+2=2\), concluding that the torus has Euler characteristic \(2\). The arithmetic is \(3-3+2=2\), but the conclusion is wrong: the outside component is a torus with a disk removed, not an open disk. This embedding is not cellular, so the cellular Euler formula cannot be applied with those two components as disk faces. The graph \(C_3\) still has both genus parameters zero because the triangle embeds in the sphere.
When determining genus from an embedding, keep the questions separate:
- Does the drawing give an embedding, with no crossings?
- Is the embedding cellular, if a surface Euler formula is being used?
- Is the surface of least possible complexity for this graph?
An explicit embedding establishes an upper bound on the relevant genus. To establish an exact positive genus, one also needs an argument that the graph cannot embed on any surface of lower complexity. For genus zero, a plane embedding already determines both parameters: their definitions make negative values impossible.
Check Your Understanding
For each question, distinguish what a particular embedding demonstrates from what the minimum defining genus requires.
- State the orientable genus and nonorientable genus of the graph with \(V=\{u,v\}\) and \(E=\{uv\}\). Give an embedding that establishes your answer.
- Explain why, under the convention used here, a planar graph has nonorientable genus \(0\), and how an alternative convention can assign it the value \(1\).
- Suppose \(H\) is obtained from \(G\) by deleting one edge. Which inequality does the subgraph proposition give for each genus parameter?
- A graph has an embedding on the torus. Does this alone imply that its orientable genus is \(1\)? Explain.
- Why is counting complementary regions not sufficient to use the cellular Euler formula for an embedding?