# Isomorphisms of Planar Embeddings

My question: How does one distinguish between two embeddings of the same graph on the plane?

For instance, are two such embeddings considered the same if the degree sequence of their faces are the same? Or does even the slightest change, such as drawing an edge more crooked in one embedding than the other, constitute a different embedding? (Or perhaps none of these?)

• After thinking for awhile, I'm now quite curious if such an example even exists. Like, does there exist a planar graph $G$ with two planar embeddings where the degrees of the faces don't match? Commented Mar 31, 2020 at 14:56

Mathematicians differ in preference about what it takes to call two objects equal as opposed to just equivalent or isomorphic...

...but at the very least, two planar embeddings should be "basically the same" if there's an isomorphism of the graphs that also preserves the faces. Or in other words if they have faces of the same degrees connected in all the same ways, just arranged differently.

Take the three examples below. These are all embeddings of the same graph; I've just tucked one or both of the 3-cycles inside the 5-cycle.

The first and second embeddings are definitely different, and also answer your question about whether face degrees must be the same. In the first, the face lengths are $$3,3,5,7$$ (including the outside face). In the second, the face lengths are $$3,3,6,6$$.

The third embedding looks very different from the first, but it shouldn't actually be considered different. Both of them have faces of lengths $$3,3,5,7$$. In both of them, the two triangular faces share a vertex with each other; each shares one edge with the face of length $$5$$, and two edges with the face of length $$7$$. And so on; there is a correspondence between the faces that preserves all the properties we care about.

You can distinguish embeddings if they are encoded as a combinatorial map. Consider the numbering of these graphs (same as Misha's answer):

A simple way to describe the embedding would be the cyclic order of the neighbours of each vertex. For an anti-clockwise direction, the graphs would be:

A: [0: [1, 5, 4], 1: [0, 2, 6, 5], 2: [1, 3, 6], ...]

B: [0: [1, 4, 5], 1: [0, 5, 2, 6], 2: [1, 3, 6], ...]

C: [0: [1, 4, 5], 1: [0, 5, 6, 2], 2: [1, 6, 3], ...]

I've only listed the vertices [0, 1, 2], as for degrees less than 3 it's always the same. However, you can see that A[2] == B[2] and B[0] == C[0] as expected.

The actual definition of a combinatorial map involves a representation of the graph where edges are split into darts and there are a pair of permutations on these darts that encode the cyclic orientation.

I assume that this definition is easier to generalise to higher dimensions, but it does not seem to add very much to the question of isomorphisms.

• But this means that A and C really are different. Commented Oct 12, 2021 at 9:35
• @Felix Goldberg Yes on re-reading both answers, I see what you mean. Misha's answer is more rigorous, mine is a description of how to encode an embedding. Maybe there is some obvious isomorphism between A and C in my scheme that I've missed... Commented Oct 14, 2021 at 21:28