The genus of a graph 
,
denoted 
or 
, is the minimum number of handles
that must be added to the plane to embed the graph without any crossings. A graph
with genus 0 is embeddable in the plane and is said to be a planar
graph. The names of graph classes having particular values for their genera are
summarized in the following table (cf. West 2000, p. 266).
The table uses exact graph genus: a graph in the row 
has 
. This differs from the inclusive embedding convention
in which, for example, a graph embeddable on a torus may
be called toroidal even when it has smaller genus.
A singlecross graph has graph genus 1, since its single crossing can be removed by adding a handle. The converse
is false: for example, the complete graphs 
and 
have graph genus 1 but graph crossing numbers 3 and 9, respectively.
Every graph has a genus (White 2001, p. 53).
The smallest double-toroidal graph have 8 vertices, and there are precisely 15 double-toroidal graphs on 8 nodes.
There are no pretzel graphs on eight or fewer vertices.
Let 
be a surface of genus 
. Then if 
for 
, then 
has in embedding in 
but not in 
for 
. Furthermore, 
embeds in 
for all 
, as can be seen by adding 
handles to an embedding of 
in 
(White 2001, p. 52).
The genus of a graph 
satisfies
 |
(1)
|
where 
is the edge count of 
(White 2001, p. 53).
The genus of a disconnected graph is the sum of the genera of its connected components (Battle et al. 1962, White 2001, p. 55), and the genus of a connected graph is the sum of the genera of its blocks (Battle et al. 1962; White 2001, p. 55; Stahl 1978).
It follows from results of Battle et al. (1962) that the disjoint union of 
copies of 
, or of 
copies of 
, is a forbidden minor
for graphs of genus 
.
Similarly, 
copies of 
or 
such that some share a vertex
and which have blocks that are 
or 
are forbidden minors for graphs of genus 
.
Duke and Haggard (1972; Harary et al. 1973) gave a criterion for the genus of all graphs on 8 and fewer vertices. Define the double-toroidal graphs
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
where 
denotes 
minus the edges of 
.
Then for any subgraph 
of 
:
1. 
if 
does not contain a Kuratowski
graph (i.e., 
or 
),
2. 
if 
contains a Kuratowski graph
(i.e., is nonplanar) but does not contain any
for 
,
3. 
if 
contains any 
for 
.
The complete graph 
has genus
![gamma(K_n)=[((n-3)(n-4))/(12)]](/images/equations/GraphGenus/NumberedEquation2.svg) |
(5)
|
for 
, where ![[x]](/images/equations/GraphGenus/Inline65.svg)
is the ceiling function
(Ringel and Youngs 1968; White 1973; Harary 1994, p. 118; Asir and Chelvam 2014).
The values for 
,
2, ... are 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000933).
The complete bipartite graph 
has genus
![gamma(K_(m,n))=[((m-2)(n-2))/4]](/images/equations/GraphGenus/NumberedEquation3.svg) |
(6)
|
(Ringel 1965; Beineke and Harary 1965; White 1973; Harary 1994, p. 119; Asir and Chelvam 2014).
White conjectured that complete tripartite graph 
with 
has genus
![gamma_(conjectured)(K_(k,m,n))=[((k-2)(m+n-2))/4]](/images/equations/GraphGenus/NumberedEquation4.svg) |
(7)
|
(Stahl and White 1976, Ellingham et al. 2005, Ellingham et al. 2006). While this has not been proven in general, it has been established in a number of special cases (White 1969b, Stahl and White 1976, Craft 1991, Craft 1998, Ellingham et al. 2005, Ellingham et al. 2006), including the case
 |
(8)
|
(White 1973, Asir and Chelvam 2014).
The complete 4-partite graph 
has genus
 |
(9)
|
(White 1973, Asir and Chelvam 2014).
The hypercube 
has genus
 |
(10)
|
(Ringel 1955; Beineke and Harary 1965; Harary et al. 1988; Harary 1994, p. 119). The values for 
,
2, ... are 0, 0, 0, 1, 5, 17, 49, 129, ... (OEIS A000337).
-Cube." Canad. J. Math. 17,
494-496, 1965.Brinkmann, G. "A Practical Algorithm for the Computation
of the Genus." 17 May 2020. 
." Israel J. Math. 11,
452-455, 1972.Ellingham, M. N.; Stephens, C.; and Zha, S. "Counterexamples
to the Nonorientable Genus Conjecture for Complete Tripartite Graphs." Europ.
J. Combin. 26, 387-399, 2005.Ellingham, M. N.; Stephens,
C.; and Zha, S. "The Nonorientable Genus of Complete Tripartite Graphs."
J. Combin. Th., Ser. B 96, 529-559, 2006.Harary, F. 
-Connected Graph." Fund. Math. 54, 7-13,
1964.Harary, F. and Palmer, E. M. 
-Octahedron: Regular Cases." J.
Graph Th. 2, 69-75, 1978.Mayer, J. "Le problème
des régions voisines sur les surfaces closes orientables." J. Combin.
Th. 6, 177-195, 1969.Metzger, A. GitHub: SanderGi/Genus.
-dimensionalen Würfel und Würfelgitter."
Abh. Math. Sem. Univ. Hamburg 20, 10-19, 1955.Ringel,
G. Färbungsprobleme auf Flachen und Graphen. Berlin: Deutsche Verlag
der Wissenschaften, 1962.Ringel, G. "Das Geschlecht des vollständiger
Paaren Graphen." Abh. Math. Sem. Univ. Hamburg 28, 139-150, 1965.Ringel,
G. and Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem."
Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.Ringel, G.
and Youngs, J. W. T. "Remarks on the Heawood Conjecture." In
." J. Combin. Th. 7, 283-285, 1969b.White,
A. T. Graphs, Groups and Surfaces. Amsterdam, Netherlands: North-Holland,
1973.White, A. T. "Imbedding Problems in Graph Theory."
Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White).
Amsterdam, Netherlands: Elsevier, pp. 49-72, 2001.