Content deleted Content added
→Terminology: cellular |
→Combinatorial embedding: Other equivalent representations |
||
Line 42:
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.
Other equivalent representations for cellular embeddings include the [[ribbon graph]], a topological space formed by gluing together topological disks for the vertices and edges of an embedded graph, and the [[graph-encoded map]], an edge-colored [[cubic graph]] with four vertices for each edge of the embedded graph.
==Computational complexity==
| |||