3
$\begingroup$

I know that nonplanar graphs can be embedded without self-intersection into a $g$-holed torus, for sufficiently large $g$. In particular, I know that $K_5$ and $K_{3,3}$ can be embedded into the torus. Similarly, I know that the four color theorem fails on the torus, requiring at most 7 colors to color a map of the torus. I am wondering about the "intermediate" surface, the cylinder.

My question, roughly, is whether there are any graph-theoretic (or "graph theory-adjacent") constructions that are admissible on the cylinder but fail on the plane. If there are, I would love a constructive example. If not, what is the property of the plane and cylinder that is shared? In my mind, since they have different fundamental groups there ought to be something different in terms of graphs. Many thanks in advance!

$\endgroup$

1 Answer 1

7
$\begingroup$

There is no difference between planar and "cylindrical" graphs.

To see this, note that an open disk on a cylinder is homeomorphic to the plane, and a cylinder is homeomorphic to an annulus, which is a subset of the plane.

So whenever you can embed a graph into a cylinder, you can embed it into an annulus on the plane. Whenever you can embed a graph on the plane, you can embed it into a disk of a cylinder. (So the property they share is that they are basically subspaces of eachother, and both subspaces of the sphere if you care just about compact surfaces)

You may find embeddings of graphs on the projective plane more interesting, as this is the "simplest" (in some sense) surface onto which some non-planar graphs can be embedded.

Here's a pic of $K_5$ on the projective plane. enter image description here

$\endgroup$
3
  • $\begingroup$ Brilliant! Thank you so much! $\endgroup$ Commented Jul 20, 2021 at 14:18
  • $\begingroup$ Can you give an example/link to such a non-planar graph and its embedding? $\endgroup$ Commented Jul 20, 2021 at 14:30
  • 1
    $\begingroup$ I would just look for some papers on "projective planar graphs" and scour the figures in them. I've added a picture of $K_5$ embedded on the projective plane for you to get an idea of how such things are normally drawn. $\endgroup$ Commented Jul 20, 2021 at 15:27

You must log in to answer this question.

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