Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Hamiltonian Paths Through Two- and Three-Dimensional Grids



William F. Mitchell


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.
Journal of Research (NIST JRES) - of
Report Number
110 No. 2


adaptive grid refinement, Hamiltonian path, load balancing, refinement-tree partition


Mitchell, W. (2005), Hamiltonian Paths Through Two- and Three-Dimensional Grids, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed April 16, 2024)
Created April 1, 2005, Updated February 19, 2017