1
$\begingroup$

The problem is this:

Can every closed triangle mesh (an approximation of a 3d object using triangles, eg. a tetrahedron) be 'peeled like an orange', that is, can we find a sequence of triangles such that consecutive triangles share edges, and all triangles in the mesh are included once (and only once) in our sequence.

This is my logic so far:

Model the mesh as its dual graph, where vertices are triangles, and edges join triangles that share edges, then the problem boils down to finding a Hamiltonian Path in the graph.

Each vertex will have degree three; this makes the graph by definition cubic.

I did some googling; I did find that Tait's conjecture, that every cubic polyhedral graph has a Hamiltonian cycle, is false. I guess then that every cubic polyhedral graph has a Hamiltonian path (otherwise a counterexample would disprove Tait's conjecture). Cubic polyhedral graphs are planar and 3-vertex-connected so if my guess is correct, we can 'peel' all convex polyhedra, but can we always 'peel' a torus?

I believe that if our 3d mesh is an object without holes, then the graph is always planar.

So my question is:

When are Hamiltonian paths guaranteed to exist in cubic graphs? Particularly those cubic graphs that correspond to physical triangle meshes.

In my quest for a counterexample I constructed a genus-2 surface out of triangles, but it was fairly easy for my computer to find a 'peeling', so I am now a little more convinced that everything can be peeled.

$\endgroup$
1
$\begingroup$

I found a paper that gives the required example.

The first graph in this paper shows an 88 vertex planar cubic graph that doesn't have any Hamiltonian path:enter image description here

The dual of this would be a 3d convex polyhedron made of 88 triangles (Garuanteed by Steinitz Theorem, as noted by Henning Makholm) that cannot be 'peeled'. It can be realised as a tetrahedron, with the base a single triangle, and the sides an arrangement of 29 triangles:

enter image description here

The example makes use of what it calls a 'Tutte Triangle': $abc$ - a graph with the property that any path joining $b$ and $c$ cannot pass through all vertices of $abc$.

$\endgroup$
0
$\begingroup$

The dual of the Tutte graph would be a counterexample to the existence of a Hamiltonian cycle. But the Tutte graph does have a Hamiltonian path.

On the other hand, we can use the Tutte fragment to construct a polyhedral 3-regular graph that doesn't even have a Hamiltonian path: Take the graph of a cube, allow two vertices opposite each other to remain vertices, and replace each of the other six vertices with a Tutte fragment "pointing towards" the selected cube vertex, producing this:

picture of two conjoined Tutte graphs

which (by Steinitz's theorem) you can draw on a sphere and dualize to get this unpeelable triangle mesh (imagine folding the figure into an octahedron):

net of resulting polyhedron


I doubt you can find an easy necessary and sufficient criterion, since the NP-hardness of finding Hamiltonian cycles seems to be quite robust.

If your triangle mesh can be 2-colored (that is, the underlying cubic graph is bipartite), a Hamiltonian cycle may be guaranteed; this is the unsolved Barnette's conjecture.

[1]:

$\endgroup$
  • $\begingroup$ Thanks, so the dual of this graph (replacing vertices with triangles) would be some triangle mesh that couldn't be peeled. Are we guaranteed that the dual of this can be realised a nice (eg. non-overlapping, finite area) 3d object? $\endgroup$ – Christian Fieldhouse Nov 11 '17 at 19:41
  • $\begingroup$ @ChristianFieldhouse: Yes, that is fairly easy to check by Steinitz's theorem. $\endgroup$ – Henning Makholm Nov 11 '17 at 19:45
  • $\begingroup$ How do you know that no Hamiltonian paths exist on this graph? I guess you could use any path to construct a Hamiltonian cycle (but I don't know how), a contradiction. Or is there a simpler way to see that no Hamiltonian Paths exist? $\endgroup$ – Christian Fieldhouse Nov 12 '17 at 10:32
  • $\begingroup$ *a Hamiltonian cycle on the Tutte Graph $\endgroup$ – Christian Fieldhouse Nov 12 '17 at 10:41
  • $\begingroup$ @ChristianFieldhouse: Hmm ... while trying to explain my argument I discovered a Hamiltonian path. Oops! The same idea will still work but we need three Tutte graphs rather than two. $\endgroup$ – Henning Makholm Nov 12 '17 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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