NIST logo

Publication Citation: Hamiltonian Paths Through Two- and Three-Dimensional Grids

NIST Authors in Bold

Author(s): William F. Mitchell;
Title: Hamiltonian Paths Through Two- and Three-Dimensional Grids
Published: April 01, 2005
Abstract: This paper addresses the existence of Hamiltonian paths and cycles in two-dimensional grids consisting of triangles or quadrilaterals, and three-dimensional grids consisting of tetrahedra or hexahedra. The paths and cycles may be constrained to pass from one element to the next through an edge, through a vertex, or be unconstrained and pass through either. It was previously known that an unconstrained Hamiltonian path exists in a triangular grid under very mild conditions, and that there are triangular grids for which there is no through-edge Hamiltonian path. In this paper we prove that a through-vertex Hamiltonian cycle exists in any triangular or tetrahedral grid under very mild conditions, and that there exist quadrilateral and hexahedral grids for which no unconstrained Hamiltonian path exists. The existence proofs are constructive, and lead to an efficient algorithm for finding a through-vertex Hamiltonian cycle.
Citation: Journal of Research (NIST JRES) - of
Volume: 110 No. 2
Keywords: adaptive grid refinement;Hamiltonian path;load balancing;refinement-tree partition
Research Areas: Software
PDF version: PDF Document Click here to retrieve PDF version of paper (900KB)