TOPICS
Search

Nonorientable Graph Genus

The nonorientable graph genus gamma^~(G) of a graph G is the minimum number k such that G can be embedded in the nonorientable surface N_k formed by adding k cross-caps to a sphere. It is also called the graph crosscap number. By convention, gamma^~(G)=0 for a planar graph (Ellingham and Stephens 2007).

The graph genus gamma(G) is the corresponding minimum over orientable surfaces and is therefore also called the orientable genus. The Euler genus of G is min{2gamma(G),gamma^~(G)}. These two invariants can behave quite differently. For example, graphs of arbitrarily large orientable genus can have nonorientable graph genus 1 (Mohar 1998).

See also

Cross-Cap, Euler Genus, Graph Embedding, Graph Genus, Nonorientable Surface, Orientable Genus

Explore with Wolfram|Alpha

References

Ellingham, M. N. and Stephens, D. C. "The Nonorientable Genus of Joins of Complete Graphs with Large Edgeless Graphs." J. Combin. Th., Ser. B 97, 827-845, 2007. https://doi.org/10.1016/j.jctb.2007.02.001.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.

Cite this as:

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

Subject classifications