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