TOPICS
Search

Graph Genus


The genus gamma(G) of a graph 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

 gamma(G)<=m
(1)

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

B_1=K_8-K_3
(2)
B_2=K_8-(2K_2 union P_3)
(3)
B_3=K_8-K_(2,3),
(4)

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

 gamma(K_n)=[((n-3)(n-4))/(12)]
(5)

for n>=3, where [x] is the ceiling function (Ringel and Youngs 1968; Harary 1994, p. 118). 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

 gamma(K_(m,n))=[((m-2)(n-2))/4]
(6)

(Ringel 1965; Beineke and Harary 1965; Harary 1994, p. 119).

The hypercube Q_n has genus

 gamma(Q_n)=1+(n-4)2^(n-3)
(7)

(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

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.Duke, R. A.; and Haggard, G. "The Genus of Subgraphs of K_8." 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 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.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.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.

Referenced on Wolfram|Alpha

Graph Genus

Cite this as:

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

Subject classifications