Orientable Genus

The orientable genus of a graph , denoted or , is the minimum number of handles that must be added to the sphere to embed the graph without any crossings. It is most commonly called simply the graph genus. A graph with orientable 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 orientable 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

The table uses exact orientable 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.

The nonorientable genus , also called the graph crosscap number, instead minimizes the number of cross-caps in a nonorientable surface containing an embedding of . The Euler genus of is the smaller of and (Mohar 1998).

A singlecross graph has orientable genus 1, since its single graph crossing can be removed by adding a handle. The converse is false: for example, the complete graphs and have orientable genus 1 but graph crossing numbers 3 and 9, respectively.

Every graph has an orientable genus (White 2001, p. 53).

The smallest double-toroidal graph has 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 an orientable surface of genus . If for , then has an 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 orientable genus of a graph satisfies

(1)

where is the edge count of (White 2001, p. 53).

The orientable genus of a disconnected graph is the sum of the orientable genera of its connected components (Battle et al. 1962; White 2001, p. 55), and the orientable genus of a connected graph is the sum of the orientable genera of its blocks (Battle et al. 1962; Stahl 1978; White 2001, p. 55).

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 orientable genus . Similarly, copies of or such that some share a vertex and which have blocks that are or are forbidden minors for graphs of orientable genus .

Duke and Haggard (1972, Harary et al. 1973) gave a criterion for the orientable 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 orientable genus

(5)

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

(6)

(Ringel 1965; Beineke and Harary 1965; White 1973; Harary 1994, p. 119; Asir and Chelvam 2014).

White conjectured that the orientable genus of the complete tripartite graph with is

(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 orientable genus

(9)

(White 1973, Asir and Chelvam 2014).

The hypercube has orientable 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).