How to judge the isomorphism of two drawings of same graph?

Question

We say two drawings of a graph are isomorphic if there is a homeomorphism of the surface that maps one drawing to the other. But in actual operation, I find it quite difficult to determine whether two drawings are isomorphic. I don’t know how to describe homeomorphism. For example, the following two drawings both show one graph $K_6$ on the plane:

Are these two drawing isomorphic? why? Is there a more operational way to judge?

The definition of drawing isomorphism comes from the following book, which is also the first monograph of Crossing number.

Crossing numbers of graphs

Answer 1

The big problem with testing if two graphs are isomorphic is that there's so many potential ways to match them up. With graph drawings, there is no combinatorial explosion - at least not when the graph drawing is $2$-connected. (If not, then we can still find isomorphisms between blocks efficiently, but it might be hard to figure out which blocks correspond.)

Treat a graph drawing as a plane embedding of a graph, in which the intersections are merely another type of vertex. If the graph drawing is $2$-connected, then each face has a face walk which visits all the vertices in order around the face, which is unique up to changing the starting point and reversing the order.

Let's make two initial guesses about the drawing isomorphism:

1. Pick a length-$k$ face of one drawing, and guess which length-$k$ face of the other drawing it corresponds to.
2. Pick face walks $v_1, \dots, v_k, v_1$ and $w_1, \dots, w_k, w_1$ of the two faces, and guess that $v_i$ corresponds to $w_i$ for $i=1, 2, \dots, k$.

Then if our guesses were right, the rest of the isomorphism is determined. The other face touching edge $v_i v_{i+1}$ must correspond to the other face touching edge $w_i w_{i+1}$, and knowing two corresponding vertices tells us how the rest of their face walks correspond. We can repeat this to grow the region where we know the isomorphism, one face at a time. Either we reach a contradiction (two faces that must match have different lengths, or two vertices that must match have different types), or we find an isomorphism.

We can try every possible way to make these guesses, and see if they work out. In the plane, we have a shortcut: the unbounded faces must correspond.