 The non-orientable genus of a graph is the minimal integer "n" such that the graph can be drawn without crossing itself on a sphere with "n" cross-caps (i.e.a non-orientable surface of (non-orientable) genus "n").