Editing Genus (mathematics) (section)

===Graph theory===
{{Main|Graph embedding}}

The '''genus''' of a [[Graph (discrete mathematics)|graph]] is the minimal integer ''n'' such that the graph can be drawn without crossing itself on a sphere with ''n'' handles (i.e. an oriented surface of the genus ''n''). Thus, a planar graph has genus 0, because it can be drawn on a sphere without self-crossing.

The '''non-orientable genus''' of a [[Graph (discrete mathematics)|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'').  (This number is also called the '''demigenus'''.)

The '''Euler genus''' is the minimal integer ''n'' such that the graph can be drawn without crossing itself on a sphere with ''n'' cross-caps or on a sphere with ''n/2'' handles.<ref>{{cite book | last=Ellis-Monaghan | first=Joanna A. | last2=Moffatt | first2=Iain | title=Graphs on Surfaces: Dualities, Polynomials, and Knots | publisher=Springer New York | publication-place=New York, NY | date=2013 | isbn=978-1-4614-6970-4 | doi=10.1007/978-1-4614-6971-1 | page=}}</ref>

In [[topological graph theory]] there are several definitions of the genus of a [[Group (mathematics)|group]]. Arthur T. White introduced the following concept. The genus of a group ''G'' is the minimum genus of a (connected, undirected) [[Cayley graph]] for ''G''.

The [[Graph embedding#Computational complexity|graph genus problem]] is [[NP-complete]].<ref>{{cite journal|first1=Carsten |last1=Thomassen |title= The graph genus problem is NP-complete |journal= Journal of Algorithms |year=1989 |issue=4 |volume=10 |pages=568&ndash;576 |issn=0196-6774 |doi=10.1016/0196-6774(89)90006-0 | zbl=0689.68071 }}</ref>