1
$\begingroup$

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

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ A triangle with an extra edge pointing in, resp. out? I don't think one can do better... $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Nov 10, 2017 at 14:10
  • 2
    $\begingroup$ For the sphere, take the triangle with two extra edges, pointing into the same, resp. different hemispheres $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Nov 10, 2017 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
    Commented Nov 10, 2017 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
    Commented Nov 10, 2017 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
    Commented Nov 10, 2017 at 14:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .