I'm reading a textbook about Graph Theory and in the section about planar graphs they give a recursive definition of a planar embedding. It is here:
Definition 5.8.2. A planar embedding of a connected graph consists of a nonempty set of closed walks of the graph called the discrete faces of the embedding. Planar embeddings are defined recursively as follows:
Base case: If $G$ is a graph consisting of a single vertex $v$, then a planar embedding of $G$ has one discrete face, namely the length zero closed walk $v$.
Constructor Case (split a face): Suppose $G$ is a connected graph with a planar embedding, and suppose $a$ and $b$ are distinct, nonadjacent vertices of $G$ that appear on some discrete face $y$ of the planar embedding. That is, $y$ is a closed walk of the form $a...b...a$ Then the graph obtained by adding the edge $\{a, b\}$ to the edges of $G$ has a planar embedding with the same discrete faces as G, except that face $y$ is replaced by the two discrete faces $a...ba$ and $ab...a$ as illustrated in Figure 5.42.
Constructor Case (add a bridge): Suppose $G$ and $H$ are connected graphs with planar embeddings and disjoint sets of vertices. Let $a$ be a vertex on a discrete face, $y$, in the embedding of $G$. That is, $y$ is of the form $a...a$. Similarly, let $b$ be a vertex on a discrete face, $z$, in the embedding of $H$. So $z$ is of the form $b...b$
Then the graph obtained by connecting $G$ and $H$ with a new edge, $\{a, b\}$, has a planar embedding whose discrete faces are the union of the discrete faces of $G$ and $H$, except that faces $y$ and $z$ are replaced by one new face $a...ab...ba$
This is illustrated in Figure 5.43, where the faces of $G$ and $H$ are:
$G$: $\{axyza, axya, ayza\}$ and $H$: $\{btuvwb, btvwb, tuvt\}$
After adding the bridge $\{a, b\}$, there is a single connected graph with faces $\{axyzabtuvwba, axya, ayza, btvwb, tuvt\}$
Source of the images and text - page 177/178 from MIT Open courseware 6-042j Textbook, linked above.
It makes kind of sense for me that they define a planar embedding based on the faces (or the closed walks that define these faces), but I don't really understand how come that there are only 2 constructor cases. Am I right in understanding that these (split face and bridge) are the only way how new walks (and therefore new embeddings) can be constructed?
And, in the end, what is this whole definition then? Can I see it as a recipe how to construct a planar embedding based on a set of edges?
I think I'm just a bit surprised that with 2 cases you can cover all possible planar embedding constructions.
After reading the wikipedia article of structural induction, I think I understand why I got confused. The confusing thing for me in the MIT textbook is, that their recursive definition looks a lot like a proof by induction, but it is I think meant as a definition only.
The recursive definition is not a proof itself (it would need to be proved separately, they also mention that later in the chapter), but more of a definition of what operations can happen that create new planar embeddings from an exsting planar embedding.
Also, the definition contains ALL operations that can happen on such an embedding, like, I can add an edge to a graph that just creates a "dongle" in the graph, but that doesn't affect properties of the planar embedding. It adds more vertices to the closed walk that defines a planar embedding of course, but the planarity of the planar embedding stays the same.
To quote from the wikipedia article, they give an example where they want to prove that if you concatenate two lists $L$ and $M$, then the length of the result will be $length\ L + length\ M$.
In order to proof this, it's needed to first define what length and what concatenation means. After these definitions are established, we can use structural induction based on the definition. Since we use induction, it makes sense that the definitions are also recursive (so that we can assume $P(n)$ for $P(n+1)$.
How does this apply then to planar embeddings then. I tried to summarize the MIT definition in my own words.
First, we define the start of all planar embeddings, a single vertex $v$. A single vertex graph has a single face, defined by the closed walk of just $v$.
Based on this, we can add edge after edge, until we reach one of the constructor cases for new planar embeddings. That can happen e. g. like this:
We have $v_1$, then connect it via an edge to $v_2$, connect that to $v_3$, connect $v_4$ to $v_3$. Until now, the graph is basically still the basecase:
From what I get from the definition, this graph has a single face defined by the closed walk $v_1,...,v_4,...,v_1$.
Finally we connect $v_4$ to $v_1$. Now we reached the constructor case "splitting face" (we got 2 faces, one in, one out).
The other possibility is bridging two graphs (the bridging edge is shown with
*here):This would mean we reached the other constructor case, "add a bridge".
Before the bridge was inserted, there were two closed walks $v_2,...v_2$ and $v_5,...,v_5$. By inserting an edge $\{v_2,v_5\}$, these two closed walks will be merged into one. So the number of edges goes up by one, the number of faces goes down by one.
I hope my undstanding of the definition makes sense, but I encourage everyone to correct me.