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?)
On
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.
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.