Graph Embedding - Terminology

Terminology

If a graph is embedded on a closed surface Σ, the complement of the union of the points and arcs associated to the vertices and edges of is a family of regions (or faces). A 2-cell embedding or map is an embedding in which every face is homeomorphic to an open disk. A closed 2-cell embedding is an embedding in which the closure of every face is homeomorphic to a closed disk.

The genus of a graph is the minimal integer n such that the graph can be embedded in a surface of genus n. In particular, a planar graph has genus 0, because it can be drawn on a sphere without self-crossing. The non-orientable genus of a graph is the minimal integer n such that the graph can be embedded in a non-orientable surface of (non-orientable) genus n.

The Euler genus of a graph is the minimal integer n such that the graph can be embedded in an orientable surface of (orientable) genus n/2 or in a non-orientable surface of (non-orientable) genus n. A graph is orientably simple if its Euler genus is smaller than its non-orientable genus.