Existence and construction of Hamiltonian paths and cycles on conforming tetrahedral meshes

Abstract

This paper addresses the existence and construction of Hamiltonian paths and Hamiltonian cycles on conforming tetrahedral meshes. The paths and cycles are constrained to pass from one tetrahedron to the next one through a vertex. For conforming tetrahedral meshes, under certain conditions which are normally satisfied in finite-element computations, we show that there exists a through-vertex Hamiltonian path between any two tetrahedra. The proof is constructive from which an efficient algorithm for computing Hamiltonian paths and cycles can be directly derived.

Keywords:

• adaptive finite element
• tetrahedral meshes
• Hamiltonian path
• Hamiltonian cycle
• mesh partitioning

2000 AMS Classifications :

• 05C38
• 65N50
• 65Y05
• 68W10

Acknowledgements

This work is partially supported by the 973 Program under the grant 2005CB321702, by China NSF under the grants 10531080 and 60873177, and by the 863 Program under the grant 2009AA01A134.