The nonorientable graph genus of a graph
is the minimum number
such that
can be embedded in the
nonorientable surface
formed by adding
cross-caps to a sphere.
It is also called the graph crosscap number. By convention,
for a planar graph
(Ellingham and Stephens 2007).
The graph genus is the corresponding minimum over orientable
surfaces and is therefore also called the orientable
genus. The Euler genus of
is
.
The two genera satisfy
|
(1)
|
There is no converse bound on orientable genus in terms of nonorientable graph genus alone. In fact, graphs of arbitrarily large orientable genus can have nonorientable graph genus 1 (Archdeacon 1996, Mohar 1998).
For a finite graph with vertex count
, edge count
, and
connected components,
|
(2)
|
For a connected graph, (Archdeacon 1996). If
is connected and simple,
contains a graph cycle, and has girth
, then
|
(3)
|
where
is the ceiling function (Archdeacon 1996). A
forest, including a single isolated
vertex, has nonorientable graph genus 0. For a disconnected simple graph
,
let
be a connected component containing a graph
cycle. The nonorientable graph genus of
is at least the girth lower bound
computed using the vertex count, edge
count, and girth of
.