Content deleted Content added
m Fixing links to disambiguation pages, replaced: graph{{dn|date=January 2016}} → graph (4) using AWB |
Peacedance (talk | contribs) m →Combinatorial embedding: Addition of link |
||
Line 39:
==Combinatorial embedding==
{{main|Rotation system}}
An embedded graph uniquely defines [[cyclic order|cyclic orders]] of edges incident to the same vertex. The set of all these cyclic orders is called a [[rotation system]]. Embeddings with the same rotation system are considered to be equivalent and the corresponding equivalence class of embeddings is called '''combinatorial embedding''' (as opposed to the term '''topological embedding''', which refers to the previous definition in terms of points and curves). Sometimes, the rotation system itself is called a "combinatorial embedding".<ref>{{citation|first1=Petra|last1=Mutzel|author1-link=Petra Mutzel|first2=René|last2=Weiskircher|title=Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings|year=2000|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=1858|pages=95–104|doi=10.1007/3-540-44968-X_10|chapter=Computing Optimal Embeddings for Planar Graphs|isbn=978-3-540-67787-1}}.</ref><ref>{{citation|last=Didjev|first=Hristo N.|contribution=On drawing a graph convexly in the plane|title=[[International Symposium on Graph Drawing|Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings]]|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=1995|volume=894|pages=76–83|doi=10.1007/3-540-58950-3_358}}.</ref><ref>{{citation|first1=Christian|last1=Duncan|first2=Michael T.|last2=Goodrich|author2-link=Michael T. Goodrich|first3=Stephen|last3=Kobourov|title=[[International Symposium on Graph Drawing|Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers]]|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=2010|pages=45–56|doi=10.1007/978-3-642-11805-0_7|volume=5849|chapter=Planar Drawings of Higher-Genus Graphs|isbn=978-3-642-11804-3}}.</ref>
An embedded graph also defines natural cyclic orders of edges which constitutes the boundaries of the faces of the embedding. However handling these face-based orders is less straightforward, since in some cases some edges may be traversed twice along a face boundary. For example this is always the case for embeddings of trees, which have a single face. To overcome this combinatorial nuisance, one may consider that every edge is "split" lengthwise in two "half-edges", or "sides". Under this convention in all face boundary traversals each half-edge is traversed only once and the two half-edges of the same edge are always traversed in opposite directions.
| |||