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

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 smallest double-toroidal graph has 9 vertices, and there are no pretzel graphs on eight or fewer vertices.

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

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

---

REFERENCES

Battle, J.; Harary, F.; and Kodama, Y. "Every Plane Graph with Nine Points has a Nonplanar Complement." Bull. Amer. Math. Soc. 68, 569-571, 1962

Battle, J.; Harary, F.; Kodama, Y.; and Youngs, J. W. T. "Additivity of the Genus of a Graph." Bull. Amer. Math. Soc. 68, 565-568, 1962.

Beineke, L. W. and Harary, F. "Inequalities Involving the Genus of a Graph and Its Thickness." Proc. Glasgow Math. Assoc. 7, 19-21, 1965.

Beineke, L. W. and Harary, F. "The Genus of the -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. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Harary, F.; Kainen, P. C.; Schwenk, A. J.; and White, A. T. "A Maximal Toroidal Graph Which Is Not a Triangulation." Math. Scand. 33, 108-112, 1973.

Harary, F. and Kodama, Y. "On the Genus of an -Connected Graph." Fund. Math. 54, 7-13, 1964.

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.

Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.

Harary, F.; Hayes, J. P.; and Wu, H.-J. "A Survey of the Theory of Hypercube Graphs." Comput. Math. Appl. 15, 277-289, 1988.

Heawood, P. J. "Map Colour Theorems." Quart. J. Math. 24, 332-338, 1890.

Heffter, L. "Über das Problem der Nachbargebiete." Ann. Math. 38, 477-508, 1891.

Jungerman, M. and Ringel, G. "The Genus of the -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.

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 Proof Techniques in Graph Theory (Ed. F. Harary). New York: Academic Press, 1969.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 251, 1990.

Sloane, N. J. A. Sequences A000337/M3874 and A000933/M0503 in "The On-Line Encyclopedia of Integer Sequences."Stahl, S. "The Embedding of a Graph--A Survey." J. Graph Th. 2, 275-298, 1978.

West, D. B. "Surfaces of Higher Genus." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 266-269, 2000.

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength