Graph Genus

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

	class
0	planar graph
1	toroidal graph
2	double-toroidal graph
3	pretzel graph

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

(5)

for , where 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

(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).