Graph Genus

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The genus of a graph G, denoted gamma(G) or g(G), 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 S_gamma be a surface of genus gamma. Then if gamma(G)=k for k>0, then G has in embedding in S_k but not in S_i for i<k. Furthermore, G embeds in S_j for all j>=k, as can be seen by adding j-k handles to an embedding of G in S_k (White 2001, p. 52).

The genus of a graph G satisfies

where m is the edge count of G (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 n copies of K_5 (or n disjoint copies of K_(3,3) is a forbidden minor for graphs of genus n-1. Similarly, n copies of K_5 or K_(3,3) such that some share a vertex and which have blocks that are K_5 or _K3,3 are forbidden minors for graphs of genus n-1.

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

where G-H denotes G minus the edges of H. Then for any subgraph G of K_8:

1. gamma(G)=0 if G does not contain a Kuratowski graph (i.e., K_5 or K_(3,3)),

2. gamma(G)=1 if G contains a Kuratowski graph (i.e., is nonplanar) but does not contain any B_i for i=1,2,3,

3. gamma(G)=2 if G contains any B_i for i=1,2,3.

The complete graph K_n has genus

for n>=3, where [x] is the ceiling function (Ringel and Youngs 1968; White 1973; Harary 1994, p. 118; Asir and Chelvam 2014). The values for n=1, 2, ... are 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000933).

The complete bipartite graph K_(m,n) has genus

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

White conjectured that complete tripartite graph K_(k,m,n) with k>=m>=n has genus

(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

(White 1973, Asir and Chelvam 2014).

The complete 4-partite graph K_(n,n,n,n) has genus

(White 1973, Asir and Chelvam 2014).

The hypercube Q_n has genus

(Ringel 1955; Beineke and Harary 1965; Harary et al. 1988; Harary 1994, p. 119). The values for n=1, 2, ... are 0, 0, 0, 1, 5, 17, 49, 129, ... (OEIS A000337).

See also

Circuit Rank, Double-Toroidal Graph, Graph Crossing Number, Planar Graph, Pretzel Graph, Rectilinear Crossing Number, Toroidal Graph

Explore with Wolfram|Alpha

References

Asir, T. and Chelvam, T. T. "On ge Genus of Generalized Unit and Unitary Cayley Graphs of a Commutative Ring." Acta Math. Hungar. 142, 444-458, 2014.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 n-Cube." Canad. J. Math. 17, 494-496, 1965.Brinkmann, G. "A Practical Algorithm for the Computation of the Genus." 17 May 2020. https://arxiv.org/abs/2005.08243.Conder, M. and Stokes, K. "New Methods for Finding Minimum Genus Embeddings of Graphs on Orientable and Non-Orientable Surfaces." Ars. Math. Contemp. 17, 1-35, 2019.Craft, D. L. "Surgical Techniques for Constructing Minimal Orientable Imbeddings of Joins and Compositions of Graphs." PhD thesis. Kalamazoo, MI: Western Michigan University, 1991.Craft, D. L. "On the Genus of Joins and Compositions of Graphs." Disc. Math. 178, 25-50, 1998.Duke, R. A.; and Haggard, G. "The Genus of Subgraphs of K_8." Israel J. Math. 11, 452-455, 1972.Ellingham, M. N.; Stephens, C.; and Zha, S. "Counterexamples to the Nonorientable Genus Conjecture for Complete Tripartite Graphs." Europ. J. Combin. 26, 387-399, 2005.Ellingham, M. N.; Stephens, C.; and Zha, S. "The Nonorientable Genus of Complete Tripartite Graphs." J. Combin. Th., Ser. B 96, 529-559, 2006.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 n-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 n-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.Metzger, A. and Ulrigg, A. "An Efficient Genus Algorithm Based on Graph Rotations." 29 Jun 2025. https://arxiv.org/abs/2411.07347.Metzger, A. GitHub: SanderGi/Genus. https://github.com/SanderGi/Genus/.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 n-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.Stahl, S. and White, A. T. "Genus Embeddings for Some Complete Tripartite Graphs." Disc. Math. 14, 279-296, 1976.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. "The Genus of Cartesian Products of Graphs." PhD thesis. East Lansing, MI: Michigan State University, 1969a.White, A. T. "The Genus of the Complete Tripartite Graph K_(mn,n,n)." J. Combin. Th. 7, 283-285, 1969b.White, A. T. Graphs, Groups and Surfaces. Amsterdam, Netherlands: North-Holland, 1973.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.

Referenced on Wolfram|Alpha

Graph Genus

Cite this as:

Weisstein, Eric W. "Graph Genus." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphGenus.html

Subject classifications