Graph embedding: Difference between revisions

Revision as of 02:59, 21 September 2016

Revision as of 03:20, 21 September 2016

Line 31:

the vertices and edges of <math>G</math> is a family of '''regions''' (or '''faces''').<ref name="gt01">{{citation|last1=Gross|first1=Jonathan|last2=Tucker|first2=Thomas W.|authorlink2= Thomas W. Tucker| title=Topological Graph Theory|publisher=Dover Publications|year=2001|isbn=0-486-41741-7}}.</ref> A '''2-cell embedding''' or '''map''' is an embedding in which every face is homeomorphic to an open disk.<ref>{{citation|last1=Lando|first1=Sergei K.|last2=Zvonkin|first2=Alexander K.|title=Graphs on Surfaces and their Applications|publisher=Springer-Verlag|year=2004|isbn=3-540-00203-0}}.</ref> 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 (discrete mathematics)|graph]] is the minimal integer ''n'' such that the graph can be embedded in a surface of [[Genus (mathematics)|genus]] ''n''. In particular, a [[planar graph]] has genus 0, because it can be drawn on a [[plane (geometry)|plane]] (or 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 embedded in a non-orientable surface of (non-orientable) genus ''n''.<ref name="gt01"/>

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.