Definition of dual graph

Question

I understand that the dual graph $G^*$ is really defined for a plane graph $G$, i.e., a graph along with an embedding into $\mathbb{R}^2$, instead of just a planar graph, but I still have difficulty understanding why it is well defined.

Say $G$ is $K_3$ and $K_4$ connected by an edge $e$, embedded into the plane in the natural way ($K_4$ is embedded as a triangle with its center). In $G^*$ there is a loop $l$ at the vertex corresponding to the unbounded face of $G$. Should $l$ cross $e$? If so, should it surround $K_3$ or $K_4$? I believe the resulting "dual graphs" are isomorphic as graphs but different as plane graphs, although the latter two seem like the same if considered as graphs on sphere. There also seem to be some freedom when connecting the unbounded face with other faces. What is the exact algorithm to draw a dual graph?

Edit: I have come to the conclusion that dual graph is well-defined up to embedding into sphere, although I can't show this rigorously.

For convenience here is the part in Combinatorial Mathematics by Douglas West about dual.

Answer 1

1. Should l cross e?

Yes, l should cross e. Consider the simpler example of a graph A-B-C-D. In this case, if the self loop across B-C doesn't cross the B-C edge, you would not be able to replicate the original graph by taking the dual of the dual.

2. If so should it surround $K_3$ or $K_4$.

Both are valid and isomorphic. For example, irrespective of which one it surrounds, i'm able to reconstruct the original graph from the dual of the corresponding dual graphs, so both are valid.

3. Is there an algorithm?

See if this helps?

Answer 2

The dual of a plane graph is a graph, and not itself a plane graph; any way you put the loop will give you an isomorphic graph, so it doesn't matter where from this point of view.

As far as whether the choices will give you equivalent embeddings on a sphere, this is not the case; in the example you give, you have 4 choices of where to put the loop; you can put it enclosing the vertex corresponding to the $K_{3}$, or you can put it enclosing the triangle corresponding to the $K_{4}$, or enclosing both, or enclosing neither. They are all different as plane graphs, they will pair up into two separate classes as embeddings on the sphere.

edit: After mentioning they are using West

In West's Introduction To Graph Theory, he gives the following definition of the graph dual:

Definition 6.1.7: The dual graph $G^*$ of a plane graph $G$ is a plane graph whose vertices correspond to the faces of $G$. The edges of $G^{*}$ correspond to the edges of $G$ as follows: If $e$ is an edge of $G$ with face $X$ on one side and face $Y$ on the other, then the endpoints of the dual edge $e^*$ joining the vertices $x$, $y$ in $G^*$ corresponding to the faces $X$ and $Y$. The order in the plane of the edges incident to $x \in V(G^{*})$ is the order of the edges bounding the face $X$ of $G$ in a walk around its boundary. (emphasis added).

This gives the notion you are looking for as to where to draw the loop; I think it suggests that the loop should contain one of $K_{3}$ or $K_{4}$, but not neither or both; however it doesn't resolve the last bit of ambiguity. This is addressed in remark 6.1.9 of the same book, but not adequately; I think this is a minor oversight made by West.