Graph embedding: Difference between revisions

Revision as of 14:43, 31 January 2016

Revision as of 20:18, 31 January 2016

Line 1:

In [[topological graph theory]], an '''embedding''' (also spelled '''imbedding''') of a [[Graph (discrete mathematics)|graph]]{{dn|date=January 2016}} <math>G</math> on a [[surface]] Σ is a representation of <math>G</math> on Σ in which points of Σ are associated to [[graph theory|vertices]] and simple arcs ([[Homeomorphism|homeomorphic]] images of [0,1]) are associated to [[graph theory|edges]] in such a way that:

* the endpoints of the arc associated to an edge <math>e</math> are the points associated to the end vertices of <math>e</math>,

* no arcs include points associated with other vertices,

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]]{{dn|date=January 2016}} 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]]{{dn|date=January 2016}} 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.

The '''maximum genus''' of a [[Graph (discrete mathematics)|graph]]{{dn|date=January 2016}} is the maximal integer ''n'' such that the graph can be 2-cell embedded in an orientable surface of [[Genus (mathematics)|genus]] ''n''.

==Combinatorial embedding==