5
$\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)!$.

$\endgroup$
6
$\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.

$\endgroup$
  • 2
    $\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 Dec 1 '16 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 Dec 1 '16 at 22:08
  • 2
    $\begingroup$ @DavidRicherby That's true, but isotopic embeddings on the sphere do not necessary remain isotopic on the plane. $\endgroup$ – Ilya Bogdanov Dec 1 '16 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 Dec 1 '16 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 Dec 2 '16 at 0:53

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.