Apologies for asking a question which probably has a well-known answer:

What is the smallest (not necessarily simple) planar graph with two non-homeomorphic embeddings into the plane?

I am interested in both the case where vertices are labelled, and also the case where they are unlabelled. (In my application, vertices are labelled, but labels need not be unique.)

As a follow-up, what is the smallest planar graph with inequivalent embeddings onto the sphere?

(In case it makes a difference, I assume that graphs are undirected.)

rootedplanar embeddings of the four two-edge graphs. If you consider unrooted embeddings into the plane, then the two-vertex graph with one bridge and one loop still has two different embeddings. $\endgroup$ – Noam Zeilberger Nov 10 '17 at 14:17