the orbits of a permutation are the equivalence classes under the equivalence relation where if there exists such that . here the exponent indicates -fold composition, so if one can get from to by some number of applications of .
here's the idea. suppose we start with an embedding of a graph in the plane. for each vertex, walk around the vertex counterclockwise and you will encounter edges in some order, ending up in the same place you started. the embedding thus defines a cyclic permutation (called a rotation) of the edges incident to the vertex. there is a sort of converse: given a rotation for each vertex, there is an embedding on some orientable surface that is consistent with those rotations.
for an edge-centric graph , an embedding of is a permutation of the set of darts whose orbits are exactly the parts of . thus assigns a cyclic permutation to each part of , i.e. each vertex. for each vertex , we define to be the cyclic permutation that is the restriction of to .
our interpretation is that tells us the arrangement of darts counterclockwise around in the embedding. such an interpretation is useful in drawings of embedded graphs.
we use to denote the set of orbits of .
we define the ordered pair to be an embedded graph. to be consistent with the definitions of unembedded graphs, we define and . we also define . the underlying graph of an embedded graph is defined to be the (unembedded) graph .
we may denote an embedded graph by .
to define the faces of the embedded graph, we define another permutation of the set of darts by composing with : then the faces of the embedded graph are defined to be the orbits of . we typically denote by .
for some purposes, it is convenient to distinguish one face, and designate it as the infinite face. any face of the embedded graph can be chosen to be the infinite face, and this freedom is exploited in the design of some algorithms.
for some graph , the application of the permutation to an entry of gives us another entry that is connected to , as is the next vertex in the orbit notice that we have .
informally, a planar dual of , is a planar graph whose vertices are the faces of and whose edges correspond to the edges of , this is demonstrated in fig-graph-emb-1, a formal definition for the dual is given in def-embgraphdual.
for an embedded graph , the dual graph (or just dual) is defined to be the embedded graph . we typically denote the dual of as .
it is not immediately obvious why the faces of correspond to the vertices of , with some imagination one may come to that conclusion by first demonstrating it on concrete graphs, i have yet to find (or write) a formal proof for this.
a primal graph and its dual (the dashed lines represent the dual).
in relation to the dual, the original graph is called the primal graph (or just the primal). note that the vertices of are the faces of .
.
deleting a dart from a permutation of is obtaining the permutation of defined as follows. deleting an edge consists of deleting the two darts of (in either order).
the contraction of an edge in is equivalent to the deletion of an edge in .
for an embedded graph , if is not a self-loop then the underlying graph of is the graph obtained from the underlying graph of by contracting .
for any face , of any embedded graph , the darts comprising are connected.
if and are connected in then they are connected in .
for any embedded graph , a set of darts forms a connected component of iff the same set forms a connected component in .
we say that an embedding of a graph is planar if it satisfies Euler's formula: , where is the number of nodes, is the number of arcs, is the number of faces, and is the number of connected components. in this case, we say is a planar embedded graph or plane graph.
let be a planar embedded graph. a nonempty set of darts forms a simple cycle in iff the set forms a simple cut in .
let and be the number of vertices, edges, and faces of an embedded graph. the euler characteristic of the embedding is . the genus of the embedding is the integer that satisfies the formula
for any face of any embedded graph , the darts comprising are connected.
Let and be darts of . where .
suppose . we claim that is a walk in , which proves the lemma. for , we have . by definition of , , so and have the same head in . thus .
if and are connected in then they are connected in .
for any embedded graph , a set of darts forms a connected component of iff the same set forms a connected component in .
for a planar embedded graph in which every face has size at least three, , where is the number of edges and is the number of vertices.
let be a planar embedded graph, and let be an edge that is not a self-loop. then is a planar embedded graph.
let be a plane graph, if is a spanning tree of then the edges form a spanning tree of .
if is a spanning tree of a plane graph , we use to denote the spanning tree of whose edges are (by duality of spanning trees). we refer to as the dual spanning tree with respect to in .
the spanning tree of a graph, along with are called the interdigitating trees of the graph.
we say a planar embedded graph is triangulated if each face's boundary has at most three edges.
an example for triangulated planar graph.