8
$\begingroup$

I feel sure that this question must have been addressed in the literature, but I can't seem to find it - I may be looking in the wrong place.

A graph is planar if it can be drawn on the plane such that no two edges intersect in an interior point. In general, there are infinitely many ways to draw a planar graph, of course. However, we can say that two such mappings are equivalent if one can be obtained from the other via continuous transformations (or isotopies), in such a way that no two edges cross along the way.

Now, the number $\pi(G)$ of equivalence classes is a finite number depending on the graph $G$. I would like to get good bounds on this number, as a function of the graph, ie the number of vertices, edges, the vertex degrees, or other properties of the graph. Do results of this type exist in the literature on planar graphs?

As an example, consider the star graph on the vertex set $0,1,...,n$, where the vertex $0$ is connected to all of the other vertices, and there are no other edges. Any drawing induces a cyclic ordering of the outer vertices, and two drawings are equivalent iff the induced cyclic ordering is the same. Therefore, in this case $\pi(G)= (n-1)!$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

It is a theorem of Whitney, that a $3$-connected planar graph has two planar embeddings (one being the other flipped over). If a graph is two-connected, then you can flip over some, but not all of the three-connected components (so you get $2^n,$ where $n$ is the number of such). Finally, if the graph is $1$-connected, you can monkey around just as you have, so the decomposition into 2- and 3- connected component should give you a (messy) formula.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ Sorry, am I misunderstanging something? Perhaps, Witney's theorem speaks on spherical embeddings? Or otherwise how can you switch the unbounded face? $\endgroup$
    – Ilya Bogdanov
    Commented Dec 1, 2016 at 21:14
  • $\begingroup$ @IlyaBogdanov If you have an embedding on the sphere, you can get one on the plane by puncturing the sphere at any point in a face and flattening it out to a planar embedding where that face is the exterior one. $\endgroup$
    – David Richerby
    Commented Dec 1, 2016 at 22:08
  • 3
    $\begingroup$ @DavidRicherby That's true, but isotopic embeddings on the sphere do not necessary remain isotopic on the plane. $\endgroup$
    – Ilya Bogdanov
    Commented Dec 1, 2016 at 22:27
  • $\begingroup$ It seems to me like the graph consisting of 2 triangles sharing an edge has 6 embeddings: 2 ways to orient one triangle, and then 3 ways to add the second triangle. Doesn't this contradict your answer? $\endgroup$
    – user2357112
    Commented Dec 1, 2016 at 23:44
  • $\begingroup$ @user2357112 I can only see two ways to add the second triangle: inside and outside the first one. $\endgroup$
    – Joao Costalonga
    Commented Dec 2, 2016 at 0:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .