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 planar graph therefore has graph genus 0.
The complete graph 
has genus
![gamma(K_n)=[((n-3)(n-4))/(12)]](/National_Library/20161007105358im_/http://mathworld.wolfram.com/images/equations/GraphGenus/NumberedEquation1.gif) |
(1)
|
for 
, where ![[x]](/National_Library/20161007105358im_/http://mathworld.wolfram.com/images/equations/GraphGenus/Inline3.gif)
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]](/National_Library/20161007105358im_/http://mathworld.wolfram.com/images/equations/GraphGenus/NumberedEquation2.gif) |
(2)
|
(Ringel 1965; Beineke and Harary 1965; Harary 1994, p. 119).
The hypercube 
has genus
 |
(3)
|
(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).
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.
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.
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
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.
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."
Weisstein, Eric W. "Graph Genus." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphGenus.html
Contact the MathWorld Team
graph genus
