0

I am new to graph theory and am confused as to whether I am researching in the right area. I am working on a project which requires creating closed contours on the surface of a cylinder, and this is an edge case. Generally my closed contours are manifold and non-intersecting, with each vertex shared by two edges. Here is a case where I have vertices (red dots) all sharing three edges (dashed red lines on the surface of a right cylindar.

Is there a way to evaluate such a path, where I can find if it is traversable, using each edge exactly once?

I thought about potentially "rolling out" the cylinder into a plane and simply treating it as a 2D path, but I wonder if the third dimension would allow for paths that would be invalid in 2D.

Should I be looking into a different area of graph theory to solve cases like this?

Thank you.

Path along a Cylinder

Thetravellingfool
  • 323

1 Answers1

1

Unfortunately this cannot be an Eulerian circuit, you cannot go across each edge once and start and finish on the same vertex. This does not change in 2D or 3D.

The easiest way of deducting if a 2D or 3D graph is an Eulerian Circuit (where you can only cross each edge once) is that all vertices must have an even degree (number of edges connected to that vertex) as you must leave and comeback to a vertex for it to be a cycle.

An Semi-Eulerian graph/Eulerian path (where you start and finish on different vertices and you cannot repeat edges) on the other had must have at the most 2 verticies with odd degrees.

I hope this helps!

James Cheng
  • 26