Graph embedding: Difference between revisions

Revision as of 17:48, 21 November 2016

Revision as of 09:26, 16 April 2017

Line 1:

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

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

* no arcs include points associated with other vertices,

* two arcs never intersect at a point which is interior to either of the arcs.

Line 28:

==Terminology==

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

the vertices and edges of <math>G</math> is a family of '''regions''' (or '''[[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.