The genus 
of a graph 
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).
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 
disjoint 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/Inline60.svg)
is the ceiling function
(Ringel and Youngs 1968; Harary 1994, p. 118). 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; Harary 1994, p. 119).
The hypercube 
has genus
 |
(7)
|
(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.Duke, R. A.; and Haggard, G. "The Genus of Subgraphs
of 
." Israel J. Math. 11,
452-455, 1972.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.Mohar, B. "An obstruction to Embedding
Graphs in Surfaces." Disc. Math. 78, 135-142, 1989.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. "Über drei kombinatorische Probleme am 
-dimensionalen Würfel und Würfelgitter." Abh.
Math. Sem. Univ. Hamburg 20, 10-19, 1955.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