Hamiltonian Paths Through Two- and Three-Dimensional Grids

Published

April 1, 2005

Author(s)

William F. Mitchell

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

Report Number

of

Volume

110 No. 2

NIST Pub Series

Journal of Research (NIST JRES)

Pub Type

NIST Pubs

Download Paper

Local Download

Keywords

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

Citation

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], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50021 (Accessed October 31, 2024)