Graph embedding: Difference between revisions

Revision as of 03:20, 21 September 2016

Revision as of 17:48, 21 November 2016

Line 29:

==Terminology==

If a graph <math>G</math> is embedded on a closed surface Σ, the complement of the union of the points and arcs associated to

the vertices and edges of <math>G</math> is a family of '''regions''' (or '''faces[[face (graph theory)|face]]s''').<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 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"/>