graph embedding

the orbits of a permutation $\text{[math]}$ are the equivalence classes under the equivalence relation where $\text{[math]}$ if there exists $\text{[math]}$ such that $\text{[math]}$ . here the exponent indicates $\text{[math]}$ -fold composition, so $\text{[math]}$ if one can get from $\text{[math]}$ to $\text{[math]}$ by some number of applications of $\text{[math]}$ .

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 $\text{[math]}$ , an embedding of $\text{[math]}$ is a permutation $\text{[math]}$ of the set of darts $\text{[math]}$ whose orbits are exactly the parts of $\text{[math]}$ . thus $\text{[math]}$ assigns a cyclic permutation to each part of $\text{[math]}$ , i.e. each vertex. for each vertex $\text{[math]}$ , we define $\text{[math]}$ to be the cyclic permutation that is the restriction of $\text{[math]}$ to $\text{[math]}$ .

we define the ordered pair $\text{[math]}$ to be an embedded graph. to be consistent with the definitions of unembedded graphs, we define $\text{[math]}$ and $\text{[math]}$ . we also define $\text{[math]}$ . the underlying graph of an embedded graph $\text{[math]}$ is defined to be the (unembedded) graph $\text{[math]}$ .
we may denote an embedded graph by $\text{[math]}$ .

our interpretation is that $\text{[math]}$ tells us the arrangement of darts counterclockwise around $\text{[math]}$ in the embedding. such an interpretation is useful in drawings of embedded graphs. an example of an broken link: blk:embedded graph and its embedding is given in broken link: blk:fig-planar-graph-1.

to define the faces of the embedded graph, we define another permutation $\text{[math]}$ of the set of darts by composing $\text{[math]}$ with $\text{[math]}$ :
$\text{[math]}$ then the faces of the embedded graph $\text{[math]}$ are defined to be the orbits of $\text{[math]}$ . we typically denote $\text{[math]}$ by $\text{[math]}$ .

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.

[cite:;taken from @graph_klein_2024 chapter 3.4 embedded graphs]

for some graph $\text{[math]}$ , the application $\text{[math]}$ of the permutation $\text{[math]}$ to an entry $\text{[math]}$ of gives us another entry $\text{[math]}$ that is connected to $\text{[math]}$ , as $\text{[math]}$ is the next vertex in the orbit $\text{[math]}$ notice that we have $\text{[math]}$ .

informally, a planar dual of $\text{[math]}$ , is a planar graph whose vertices are the faces of $\text{[math]}$ and whose edges correspond to the edges of $\text{[math]}$ , this is demonstrated in graph_embedding.html, a formal definition for the dual is given in graph_embedding.html.

for an embedded graph $\text{[math]}$ , the dual graph (or just dual) is defined to be the embedded graph $\text{[math]}$ . we typically denote the dual of $\text{[math]}$ as $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 chapter 3.4 embedded graphs]

it is not immediately obvious why the faces of $\text{[math]}$ correspond to the vertices of $\text{[math]}$ , with some imagination one may come to that conclusion by first demonstrating it on concrete graphs, the formal proof of deals with vector spaces and is included .

the dual of a planar embedded graph is planar.

$\text{[math]}$ in relation to the dual, the original graph $\text{[math]}$ is called the primal graph (or just the primal). note that the vertices of $\text{[math]}$ are the faces of $\text{[math]}$ .

$\text{[math]}$ .
[cite:;taken from @graph_klein_2024 chapter 3.4 embedded graphs]

deleting a dart $\text{[math]}$ from a permutation $\text{[math]}$ of $\text{[math]}$ is obtaining the permutation $\text{[math]}$ of $\text{[math]}$ defined as follows.
$\text{[math]}$ deleting an edge $\text{[math]}$ consists of deleting the two darts of $\text{[math]}$ (in either order).
[cite:;taken from @graph_klein_2024 chapter 3.4.7 deletion]

the contraction of an edge in $\text{[math]}$ is equivalent to the deletion of an edge in $\text{[math]}$ .
for an embedded graph $\text{[math]}$ , if $\text{[math]}$ is not a self-loop then the underlying graph of $\text{[math]}$ is the graph obtained from the underlying graph of $\text{[math]}$ by contracting $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 3.4.7]

for any face $\text{[math]}$ , of any embedded graph $\text{[math]}$ , the darts comprising $\text{[math]}$ are connected.
[cite:;taken from @graph_klein_2024 lemma 3.4.3]

if $\text{[math]}$ and $\text{[math]}$ are connected in $\text{[math]}$ then they are connected in $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 corollary 3.4.4]

for any embedded graph $\text{[math]}$ , a set of darts forms a connected component of $\text{[math]}$ iff the same set forms a connected component in $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 corollary 3.4.5]

a graph is planar if it has a planar embedding.

we say that an embedding $\text{[math]}$ of a graph $\text{[math]}$ is planar if it satisfies euler's formula: $\text{[math]}$ , where $\text{[math]}$ is the number of nodes, $\text{[math]}$ is the number of arcs, $\text{[math]}$ is the number of faces, and $\text{[math]}$ is the number of connected components. in this case, we say $\text{[math]}$ is a planar embedded graph or plane graph.
[cite:;taken from @graph_klein_2024 chapter 4.1 planar embeddings]

let $\text{[math]}$ be a planar embedded graph. a nonempty set of darts forms a simple cycle in $\text{[math]}$ iff the set forms a simple cut in $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 theorem 4.6.2]

let $\text{[math]}$ and $\text{[math]}$ be the number of vertices, edges, and faces of an embedded graph. the euler characteristic of the embedding is $\text{[math]}$ . the genus of the embedding is the integer $\text{[math]}$ that satisfies the formula
$\text{[math]}$ [cite:;taken from @graph_klein_2024 chapter 3.4.2 euler characteristic and genus]

an embedding is planar if its genus is 0.

for any face $\text{[math]}$ of any embedded graph $\text{[math]}$ , the darts comprising $\text{[math]}$ are connected.
[cite:;taken from @graph_klein_2024 corollary 3.4.3]

Let $\text{[math]}$ and $\text{[math]}$ be darts of $\text{[math]}$ . $\text{[math]}$ where $\text{[math]}$ .
suppose $\text{[math]}$ . we claim that $\text{[math]}$ is a walk in $\text{[math]}$ , which proves the lemma. for $\text{[math]}$ , we have $\text{[math]}$ . by definition of $\text{[math]}$ , $\text{[math]}$ , so $\text{[math]}$ and $\text{[math]}$ have the same head in $\text{[math]}$ . thus $\text{[math]}$ .

if $\text{[math]}$ and $\text{[math]}$ are connected in $\text{[math]}$ then they are connected in $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 corollary 3.4.4]

for a planar embedded graph in which every face has size at least three, $\text{[math]}$ , where $\text{[math]}$ is the number of edges and $\text{[math]}$ is the number of vertices.

let $\text{[math]}$ be a planar embedded graph, and let $\text{[math]}$ be an edge that is not a self-loop. then $\text{[math]}$ is a planar embedded graph.
[cite:;taken from @graph_klein_2024 chapter 4.2 contraction preserves planarity]

let $\text{[math]}$ be a plane graph, if $\text{[math]}$ is a spanning tree of $\text{[math]}$ then the edges $\text{[math]}$ form a spanning tree of $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 corollary 4.5.2]

if $\text{[math]}$ is a spanning tree of a plane graph $\text{[math]}$ , we use $\text{[math]}$ to denote the spanning tree of $\text{[math]}$ whose edges are $\text{[math]}$ (by duality of spanning trees). we refer to $\text{[math]}$ as the dual spanning tree with respect to $\text{[math]}$ in $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 chapter 4.5 interdigitating trees]

the spanning tree $\text{[math]}$ of a graph, along with $\text{[math]}$ are called the interdigitating trees of the graph.
[cite:;taken from @graph_klein_2024 chapter 4.5 interdigitating trees]

we say a planar embedded graph is triangulated if each face's boundary has at most three edges.
[cite:;taken from @graph_klein_2024 chapter 5.1 triangulation]

$\text{[math]}$

there is a linear-time algorithm that, given a a planar embedded graph $\text{[math]}$ , adds a set of artificial edges to obtain a triangulated planar embedded graph such that the number of artificial edges is at most twice the number of original edges.
[cite:;taken from @graph_klein_2024 problem 5.1.1]