GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Algebra
  • Applied Mathematics
  • Calculus and Analysis
  • Discrete Mathematics
  • Foundations of Mathematics
  • Geometry
  • History and Terminology
  • Number Theory
  • Probability and Statistics
  • Recreational Mathematics
  • Topology
  • Alphabetical Index
  • Random Entry
  • New in MathWorld

This view

  • Original page
  • New address

GeezerVison is showing mathworld.wolfram.com — Orientable Genus -- from Wolfram MathWorld

Search

Orientable Genus

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The orientable genus of a graph G, denoted gamma(G) or g(G), 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).

gammaclass
0planar graph
1toroidal graph
2double-toroidal graph
3pretzel graph

The table uses exact orientable genus: a graph in the row gamma=k has gamma(G)=k. 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 gamma^~(G), also called the graph crosscap number, instead minimizes the number of cross-caps in a nonorientable surface containing an embedding of G. The Euler genus of G is the smaller of 2gamma(G) and gamma^~(G) (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 K_6 and K_7 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 S_gamma be an orientable surface of genus gamma. If gamma(G)=k for k>0, then G has an 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 orientable genus of a graph G satisfies

gamma(G)<=m,
(1)

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

For a finite graph G with vertex count n>=1, edge count m, and c connected components,

gamma(G)<=|_(m-n+c)/2_|,
(2)

where |_x_| is the floor function. For a connected graph, c=1 (Archdeacon 1996). If G is connected and simple, contains a graph cycle, and has girth r>=3, then

gamma(G)>=max{0,[((r-2)m-r(n-2))/(2r)]},
(3)

where [x] is the ceiling function (Archdeacon 1996). A forest, including a single isolated vertex, has orientable genus 0.

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 n copies of K_5, or of n copies of K_(3,3), is a forbidden minor for graphs of orientable 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 K_(3,3) are forbidden minors for graphs of orientable genus n-1.

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

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

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)) as a graph minor,

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

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

The complete graph K_n has orientable genus

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

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

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

for m,n>=2 (Ringel 1965; Beineke and Harary 1965; White 1973; Harary 1994, p. 119; Asir and Chelvam 2014). If either part has size 0 or 1, the complete bipartite graph is a forest and has orientable genus 0.

White conjectured that the orientable genus of the complete tripartite graph K_(k,m,n) with k>=m>=n>=1 is

gamma_(conjectured)(K_(k,m,n))=[((k-2)(m+n-2))/4]
(9)

(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

gamma(K_(n,n,n))=((n-1)(n-2))/2
(10)

(White 1973, Asir and Chelvam 2014).

For a positive integer n, the complete multipartite graph K_(n,n,n,n) has orientable genus

gamma(K_(n,n,n,n))={5 for n=3; (n-1)^2 otherwise.
(11)

(White 1973, Asir and Chelvam 2014).

The hypercube graph Q_n has orientable genus

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

for n>=2, with gamma(Q_1)=0 (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, Euler Genus, Graph Basis Number, Graph Crossing Number, Graph Genus, Nonorientable Graph Genus, Planar Graph, Pretzel Graph, Rectilinear Crossing Number, Singlecross Graph, Toroidal Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

  • 1000th twin prime
  • GF(101)
  • mirror transformation matrix

References

Archdeacon, D. "Topological Graph Theory: A Survey." Congr. Numer. 115, 5-54, 1996.Asir, T. and Chelvam, T. T. "On the 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. https://doi.org/10.1007/BF02761469.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.; Hayes, J. P.; and Wu, H.-J. "A Survey of the Theory of Hypercube Graphs." Comput. Math. Appl. 15, 277-289, 1988.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, 1973a.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973b.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. GitHub: SanderGi/Genus. https://github.com/SanderGi/Genus/.Metzger, A. and Ulrigg, A. "An Efficient Genus Algorithm Based on Graph Rotations." 29 Jun 2025. https://arxiv.org/abs/2411.07347.Millichap, C. and Salinas, F. "Embedding Grid Graphs on Surfaces." 18 Apr 2022. https://arxiv.org/abs/2104.12270.Mohar, B. "An Obstruction to Embedding Graphs in Surfaces." Disc. Math. 78, 135-142, 1989.Mohar, B. "On the Orientable Genus of Graphs with Bounded Nonorientable Genus." Disc. Math. 182, 245-253, 1998. https://doi.org/10.1016/S0012-365X(97)00144-1.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. Färbungsprobleme auf Flachen und Graphen. Berlin, Germany: 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. 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.Wan, L. "The Genus of a Graph: A Survey." Symmetry 15, No. 2, Art. 322, 2023.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.

Cite this as:

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

Subject classifications

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.