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

  • 2
    $\begingroup$ A triangle with an extra edge pointing in, resp. out? I don't think one can do better... $\endgroup$ – მამუკა ჯიბლაძე Nov 10 '17 at 14:10
  • 2
    $\begingroup$ For the sphere, take the triangle with two extra edges, pointing into the same, resp. different hemispheres $\endgroup$ – მამუკა ჯიბლაძე Nov 10 '17 at 14:11
  • 2
    $\begingroup$ If we don't have to be simple, then a double edge will serve in place of a triangle. $\endgroup$ – Ben Barber Nov 10 '17 at 14:12
  • 3
    $\begingroup$ if you allow non-simple graphs, the triangle can be degenerate (i.e. two parallel edges, or even a loop --- if loops are allowed) $\endgroup$ – Dima Pasechnik Nov 10 '17 at 14:13
  • 3
    $\begingroup$ Hello Ross! You might also have a look at Tutte's census paper, in particular Figures 3 and 4. Figure 3 shows the nine different rooted planar 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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.