Hamiltonian paths through two- and three-dimensional grids.

This paper address 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.

Key words: adaptive grid refinement; Hamiltonian path; load balancing; refinement-tree partition.

**********

1. Introduction

Adaptive grid refinement has been shown to be an effective tool for reducing the size of the grid (and consequently the linear system) required for a given accuracy when numerically solving partial differential equations. Problems involving singularities or multi-scale behavior practically require adaptive refinement. When implemented for parallel computers, dynamic load balancing is required to keep all of the processors busy. This involves partitioning the grid into equal sized pieces (in some measure), and distributing the data among the processors accordingly. Many of the methods for computing a partition are based on a linearization of the elements (or path through the elements) in a two-dimensional or three-dimensional grid, and then cutting the linear sequence into pieces of equal size. Some of the methods that fall into this category are the space filling curves [1], OCTREE [2], and refinement-tree [3] methods. Further information on partitioning methods can be found in Ref. [4].

The space filling curve and OCTREE methods are not guaranteed to create connected partitions, which may be a desirable property. The refinement-tree method is guaranteed to give connected partitions provided that an appropriate linearization of the initial coarse grid is given. Such a linearization would be a Hamiltonian path, i.e., a path which passes from an element to a neighboring element and goes through each element exactly once. Heber et al. [5] proved that, for grids consisting of triangles, a Hamiltonian path always exists under very mild conditions. Moreover, the proof is a constructive proof which leads to an efficient algorithm to find a Hamiltonian path. However, the refinement-tree partitioning algorithm requires a stronger result in which the Hamiltonian path always passes through vertices when moving from one element to the next (as opposed to passing through edges), and does not go out the same vertex through which it came in. We call this a through-vertex Hamiltonian path. Heber's algorithm produces Hamiltonian paths that pass through both vertices and edges. Additionally, Ref. [5] only addresses triangles, not the other elements considered in this paper.

The main result of this paper is the proof that there always exists a through-vertex Hamiltonian path in grids consisting of triangles or tetrahedra, under very mild conditions. The proof is constructive, which leads to an algorithm to construct such a path. We do not explicitly give the algorithm in this paper, but it follows easily from the proofs of the main theorems. Little is known about the conditions under which a Hamiltonian path exists in grids consisting of quadrilaterals or hexahedra. An algorithm is given that might find a through-vertex Hamiltonian path in a quadrilateral or hexahedral grid, if one exists, and is likely to give a broken path with a small number of discontinuities, i.e., something close to a through-vertex Hamiltonian path.

The remainder of the paper is organized as follows. In Sec. 2 we introduce the notation and define the terms used in this paper. Section 3 addresses triangles and tetrahedra. It reviews previously known results and presents the main results of this paper. In Sec. 4 we discuss quadrilaterals and hexahedra. Section 5 contains the conclusions.

2. Definitions

For the purposes of this paper, an element, E, is a triangle, quadrilateral, tetrahedron, or hexahedron. An element contains vertices, v, and edges, e, with the obvious definitions, and three-dimensional elements contain faces, f.

A grid, G, is the union of a collection of elements, {[E.sub.i]}, all of the same kind, such that G = [union] [E.sub.i] is a connected, bounded region in [R.sup.2] or [R.sup.3], and [[degrees].E.sub.i] [intersection] [[degrees].E.sub.j] = [phi], i [not equal to] j, where [[degrees].E] denotes the interior of element E, and [phi] is the empty set. We say that [E.sub.i] is an element of G, [E.sub.i] [member of] G. A vertex of [E.sub.i] is a boundary vertex if it lies on the boundary of G, and an interior vertex if it is not a boundary vertex. We say the size of G, |G|, is N if there are N elements in G. A triangular grid, quadrilateral grid, tetrahedral grid, and hexahedral grid is a grid consisting entirely of triangles, quadrilaterals, tetrahedra and hexahedra, respectively.

A grid is said to be conforming if [E.sub.i] [intersection] [E.sub.j], i [not equal to] j, is a common vertex, common edge, common face or empty. A vertex of an element is called a hanging node if it lies in the interior of an edge or face of another element. It follows immediately from the definition that a conforming grid has no hanging nodes. A grid is said to be I-nonconforming if there is at least one hanging node in the grid, all edges contain at most one hanging node, the interior of all faces contain at most one hanging node, and the intersection of two elements is a vertex, edge or face of one of the elements, or empty. See Fig. 1 for examples of conforming and 1-nonconforming grids. This paper will primarily consider triangular and tetrahedral grids that are conforming, and quadrilateral and hexahedral grids that are conforming or 1-nonconforming.

A path with length n in a grid G is a sequence of elements, [E.sub.1][E.sub.2] ... [E.sub.n], [E.sub.i] [member of] G, i = 1, n, with [E.sub.i] [intersection] [E.sub.i+1] [not equal to] [phi], and [E.sub.i] [not equal to] [E.sub.i+1], i = 1, n - 1. A cycle of length n is a path of length n + 1 in which [E.sub.1] = [E.sub.n+1]. A Hamiltonian path is a path in which every element in G appears exactly once. A Hamiltonian cycle is a cycle in which every element in G appears exactly once except for [E.sub.1] = [E.sub.n+1], which appears exactly twice.

A sequence of elements [E.sub.1][E.sub.2] ... [E.sub.n] for which there exists an i with [E.sub.i] [intersection] [E.sub.i+1] = [phi] is called a broken path, and the sequence [E.sub.i][E.sub.i+1] is called a discontinuity in the path.

A through-vertex path (through-vertex cycle) is a path (cycle) in which the passage from one element to the next is specified as a common vertex, and the path does not pass through the same vertex when entering and exiting an element. Specifically, it is [E.sub.1][v.sub.1][E.sub.2][v.sub.2] ... [v.sub.n-1][E.sub.n] where [v.sub.i] [??] [E.sub.i] [intersection] [E.sub.i+1], i = 1, n - 1, [v.sub.i] [not equal to] [v.sub.i+1], i = 1, n - 2, and [E.sub.1][E.sub.2] ... [E.sub.n] is a path (cycle). We say that the path passes through [v.sub.i] when going from [E.sub.i] to [E.sub.i+1], and that we come into [E.sub.i] through the in-vertex [v.sub.i-1] and leave [E.sub.i] through the out-vertex [v.sub.i]. A through-edge path and cycle, and through-face path and cycle are defined similarly. A through-vertex Hamiltonian path is a through-vertex path that is also a Hamiltonian path, and the definitions of the obvious similar terms are similar. An unconstrained path is one that may pass through any of vertices, edges or faces. Although the term is redundant, we will use it when we want to emphasize that the path is not constrained to pass through only vertices, edges or faces.

A vertex, v, is called a cut vertex if G \ v is disconnected. See Fig. 2. A local cut vertex is a vertex whose removal causes G to become disconnected locally. Formally, v is a local cut vertex if there exists an R > 0 such that for all 0 < [member of] < R, (G [intersection] B (v, [member of])) \ v is disconnected, where B (v, [member of]) is the ball of radius [member of] centered at v. Note that a cut vertex is also a local cut vertex. Figure 2(b) illustrates a local cut vertex that is not a cut vertex. In three dimensions, the terms cut edge and local cut edge are defined similarly.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

3. Triangles and Tetrahedra

In this section we present what is known about the existence of the different types of Hamiltonian paths and cycles for conforming triangular and tetrahedral grids. We begin with a review of previously published results. We then give the main results of this paper, which are the existence of through-vertex Hamiltonian cycles under very mild conditions. Counterexamples are presented throughout to show conditions under which Hamiltonian cycles and paths do not exist, and to show that the conditions in the hypotheses of the theorems are essential.

Note that the existence of a cycle implies the existence of a path. Therefore most of the existence statements are made for cycles, and it is understood that the same statement holds for paths.

Conversely, non-existence statements are usually made about paths, and it is understood that the same statement holds for cycles. The exceptions to this are when quoting statements from other papers and when a path exists but a cycle does not.

The following theorem is due to Heber et al. [5].

Theorem 1 There exists a Hamiltonian path for any conforming triangular grid that contains no local cut vertices.

The statement of the theorem in Ref. [5] does not mention the absence of local cut vertices or that the grid must be conforming, however the definition of a grid in that paper is that it be a "simplicial complex coming from the simplicial decomposition of a connected 2D manifold" which implies these conditions. The theorem also holds for Hamiltonian cycles, simply by starting the base case in Heber's inductive proof with a Hamiltonian cycle between two triangles. The hypotheses of the theorem need to be extended slightly because the definition of a cycle assumes at least two elements.

Corollary 1 There exists a Hamiltonian cycle for any conforming triangular grid, of size at least 2, that contains no local cut vertices.

Hamiltonian paths and cycles also exist for tetrahedral grids under similar conditions. This follows immediately from Theorem 2 later in this section.

The following counterexamples show that the absence of cut vertices is an essential condition for Theorem 1, and the absence of local cut vertices is an essential condition for Corollary 1. However, it is not known whether the absence of local cut vertices is essential for the Hamiltonian path.

Counterexample 1 There exists a triangular grid containing cut vertices for which there is no Hamiltonian path. See Fig. 3.

Counterexample 2 There exists a triangular grid containing local cut vertices (but no cut vertices) for which there is no Hamiltonian cycle. See Fig. 4.

Corollary 1 says that, under very mild conditions, we can always find a Hamiltonian cycle (and hence a Hamiltonian path) in a triangular grid. This is an unconstrained Hamiltonian cycle, i.e., it does not say whether the passage from one element to the next is through a vertex or edge. Indeed, the recursive algorithm implied by the proof of Theorem 1 in Ref. [5] will usually result in passages through both vertices and edges. The obvious question is whether or not through-vertex Hamiltonian cycles or paths and through-edge Hamiltonian cycles or paths exist. The following well-known counterexample shows that we cannot expect to find a through-edge Hamiltonian path in a triangular grid. In fact, determining whether or not a through-edge Hamiltonian cycle exists in a triangular grid is known to be NP-complete [6]. A similar counterexample can be constructed for through-face Hamiltonian paths in tetrahedral grids.

Counterexample 3 There exists a conforming triangular grid with no local cut vertices for which there is no through-edge Hamiltonian path. See Fig. 5.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

The situation is less grim for through-vertex Hamiltonian cycles. The main result of this paper is that through-vertex Hamiltonian cycles exist for triangular and tetrahedral grids under conditions similar to those for the existence of an unconstrained Hamiltonian cycle. They again require a conforming grid with no local cut vertices. Triangular grids also require that there be at least one interior vertex, and tetrahedral grids also require that there be no local cut edges.

The following lemma says that, under conditions that will arise in the proofs of the main theorems, we can always find two triangles that share a edge, or two tetrahedra that share a face.

Lemma 1 Let G be a conforming triangular (tetrahedral) grid with |G| [greater than or equal to] 2, no local cut vertices and no local cut edges. Let [G.sub.1] [subset] G contain no local cut vertices and no local cut edges, [G.sub.2] = G \ [G.sub.1], |[G.sub.1]| [greater than or equal to] 1, and |[G.sub.2]| [greater than or equal to] 1. Then

1. there exists [E.sub.1], [E.sub.2] [member of] G such that [E.sub.1] [intersection] [E.sub.2] is a common edge (face), and

2. there exists [E.sub.1] [member of] [G.sub.1] and [E.sub.2] [member of] [G.sub.2] such that [E.sub.1] [intersection] [E.sub.2] is a common edge (face).

Proof: For part 1, suppose there are no elements that share an edge (face). Then all connections between elements are vertices (or edges), which must then be local cut vertices (or local cut edges) contradicting the hypothesis that there are no local cut vertices or local cut edges.

For part 2, suppose there is no element in [G.sub.2] that shares an edge (face) with an element in [G.sub.1]. Then [G.sub.1] and [G.sub.2] are connected by only vertices (and edges), which must then be local cut vertices (or local cut edges). [square]

We first give the main result for tetrahedral grids, where the proof is shorter.

Theorem 2 Let G be a conforming tetrahedral grid with |G| [greater than or equal to] 2. If G contains no local cut vertices and no local cut edges then there exists a through-vertex Hamiltonian cycle for G.

Proof: We prove this by induction on |[G.sub.1]| where [G.sub.1] [??] G, [G.sub.1] satisfies the hypotheses of the theorem, and we can exhibit a through-vertex Hamiltonian cycle for [G.sub.1].

For |[G.sub.1]| = 2, let [G.sub.1] = {[E.sub.1], [E.sub.2]} where [E.sub.1] and [E.sub.2] are any two elements that share a common face. Lemma 1 insures the existence of these elements. Let [v.sub.1] and [v.sub.2] be two of the vertices that they share. Then [E.sub.1][v.sub.1][E.sub.2][v.sub.2][E.sub.1] is a through-vertex Hamiltonian cycle for this subgrid.

By induction, let k = |[G.sub.1]| and suppose we have [G.sub.1] [subset] G, k [greater than or equal to] 2. [G.sub.1] satisfies the hypotheses of the theorem, and [E.sub.1][v.sub.1][E.sub.2][v.sub.2] ... [E.sub.k][v.sub.k][E.sub.1] is a through-vertex Hamiltonian cycle for [G.sub.1]. The grid and cycle can be extended to size k + 1 as follows.

Let [E.sub.k+1] [member of] G \ [G.sub.1] be an element that shares a face with some element [E.sub.1] [member of] [G.sub.1]. The existence of [E.sub.k+1] is guaranteed by Lemma 1. Without loss of generality, assume [E.sub.i] is not [E.sub.1] (otherwise, just start the numbering of the cycle with a different element). Since [E.sub.i] has only four vertices, one of the three vertices shared by [E.sub.i] and [E.sub.k+1] must be either [E.sub.i]'s in-vertex [v.sub.i-1] or [E.sub.i]'s out-vertex [v.sub.i]. Without loss of generality, suppose it is [v.sub.i] (otherwise, just reverse the ordering of the cycle). One of the three shared vertices, say v, must not be [v.sub.i-1] or [v.sub.i]. Then a through-vertex Hamiltonian cycle in [G.sub.1] [union] [E.sub.k+1] is [E.sub.1] ... [v.sub.i-1][E.sub.i]v[E.sub.k+1][v.sub.i][E.sub.i+1] ... [E.sub.1]. [square]

The proof for triangular grids is also a constructive proof that begins with a cycle through two elements and inductively extends this cycle to the complete grid. However, it is a more complicated proof because, in the notation of Theorem 2, we cannot guarantee that [E.sub.k+1] shares a vertex with [E.sub.i] that is not [v.sub.i-1] or [v.sub.i]. In that case, a more complicated extension of the cycle must be performed.

Theorem 3 Let G be a conforming triangular grid with |G| [greater than or equal to] 2. If G contains no local cut vertices and has at least one interior vertex then there exists a through-vertex Hamiltonian cycle for G.

Proof: As in Theorem 2. we prove this by induction on |[G.sub.1]|, and the base case with two triangles is trivial. By induction, suppose we have [G.sub.1] [subset] G, |[G.sub.1]| = k [greater than or equal to] 2, [G.sub.1] contains no local cut vertices, and [E.sub.1][v.sub.1][E.sub.2][v.sub.2] ... [E.sub.k][v.sub.k][E.sub.1] is a through-vertex Hamiltonian cycle for [G.sub.1]. The grid and cycle can be extended to a larger size as follows.

Let [E.sub.k+1] [member of] G \ [G.sub.1] be an element that shares an edge with some element [E.sub.i] [member of] [G.sub.1]. The existence of [E.sub.k+1] is guaranteed by Lemma 1. Without loss of generality, assume [E.sub.i] is not [E.sub.1] (otherwise, just start the numbering of the cycle with a different element). One of the two vertices that [E.sub.k+1] shares with [E.sub.i] must be either [E.sub.i]'s in-vertex, [v.sub.i-1], or [E.sub.i]'s out-vertex, [v.sub.i]. Without loss of generality, assume it shares the out-vertex (otherwise, just reverse the order of the cycle). There are four cases to consider.

Case 1. [E.sub.k+1] does not contain [v.sub.i-1]. This is the easy case that corresponds to the proof of Theorem 2. Let v be the other vertex shared by [E.sub.k+1] and [E.sub.i]. Then the new cycle is [E.sub.1] ... [v.sub.i-1][E.sub.i]v[E.sub.k+1][v.sub.i][E.sub.i+1] ... [E.sub.1]. This extension is illustrated in Fig. 6. The arrows pointing from a vertex to the interior of a triangle or from the interior of a triangle to a vertex denote the in-vertex and out-vertex, respectively.

Case 2. [E.sub.k+1] contains [v.sub.i-1] and there is another triangle, [E.sub.k+2], not on the current cycle, that shares an edge and [v.sub.i] with [E.sub.k+1].

This case is illustrated in Fig. 7. Let v be the other vertex shared by [E.sub.k+1] and [E.sub.k+2]. Then the new cycle is [E.sub.1] ... [v.sub.i-1][E.sub.i][v.sub.i][E.sub.k+1]v[E.sub.k+2][v.sub.i][E.sub.i+1] ... [E.sub.1].

Case 3. [E.sub.k+1] contains [v.sub.i-1] and there is another triangle, [E.sub.k+2], that is on the current cycle and shares an edge and [v.sub.i] with [E.sub.k-1].

First note that [E.sub.k+1] must contain both the in-vertex and out-vertex of [E.sub.k+2], otherwise we could apply case 1 with [E.sub.k+2] as [E.sub.i] to add [E.sub.k+1] to the cycle. Also note that whenever a triangle not on the cycle contains both the in-vertex and out-vertex of a triangle that is on the cycle, we can "swap" this triangle with the other triangle by removing the other triangle from the cycle and inserting the new triangle in its place, as illustrated in Fig. 8.

[FIGURE 6 OMITTED]

[FIGURE 7 OMITTED]

[FIGURE 8 OMITTED]

Case 3a. [v.sub.i] is an interior vertex.

Swap elements around [v.sub.i] until either

1. there are two adjacent elements that are not in the cycle (then apply case 2), or

2. there are adjacent elements, one on the cycle and one not on the cycle, where the one not on the cycle does not contain both the in-vertex and out-vertex of the one on the cycle (then apply case 1).

Note that if we do not encounter two adjacent elements that are not in the cycle (the first subcase), then we must eventually reach the second subcase because the other triangle adjacent to [E.sub.i] cannot contain the in-vertex of [E.sub.i], [v.sub.i-1]. See Fig. 9.

Case 3b. [v.sub.i] is a boundary vertex.

This implies that all three vertices of [E.sub.k+1] are on the boundary, for if not we could select a different [E.sub.i], [v.sub.i-1] and [v.sub.i] (possibly reversing the order of the cycle) such that an interior vertex of [E.sub.k+1] is [v.sub.i]. This leads to a natural decomposition of G into three components plus [E.sub.k+1] as illustrated in Fig. 10. The intersection of any two components is a vertex of [E.sub.k+1]. Each component contains a triangle that shares an edge with [E.sub.k+1] because there are no local cut vertices. One component contains [E.sub.i] and a second component contains [E.sub.k+2]. If the third component is not empty, let E be the element that shares an edge with [E.sub.k+1]. If E is not on the cycle, then apply case 2 (reversing the order of the cycle if necessary). If E is on the cycle and [E.sub.k+1] does not contain both the in-vertex and out-vertex of E, then apply case 1 with E as [E.sub.i]. Thus we can assume that [E.sub.k+1] contains the in-vertex and out-vertex of all adjacent triangles, so it can be swapped with any of them.

Pick an interior vertex of G, [v.sub.int]. Swap [E.sub.k+1] with the neighbor that is in the same component as [v.sub.int]. Apply case 1, 2 or 3a to reinsert the other element, if appropriate. If not, then consider the decomposition around the new element and repeat the process (see Fig. 11). The component that contains [v.sub.int] has at least lost the swapped triangle, and thus is smaller in this decomposition. Since the size of the component containing [v.sub.int] will continue to shrink with each application of this process, it must eventually lead to [v.sub.int], at which point case 3a applies, unless it ends earlier by applying case 1, 2 or 3a.

[FIGURE 9 OMITTED]

Case 4. [E.sub.k+1] contains [v.sub.i-1] and there is no other triangle that shares an edge and [v.sub.i] with [E.sub.k+1], i.e., that edge is on the boundary.

Then there must be another triangle that shares [v.sub.i] and an edge with [E.sub.i], for if that edge of [E.sub.i] was also on the boundary, then [v.sub.i] would be a local cut vertex. Swap [E.sub.k+1] with [E.sub.i], and then apply either case 2 or case 3 to add [E.sub.i] back into the path. [square]

The inclusion of an interior vertex is an essential condition for Theorem 3. The same counterexample can be used as was used in Counterexample 3. However, this example does contain a through-vertex Hamiltonian path. It is not known whether or not the inclusion of an interior vertex is essential for the existence of a through-vertex Hamiltonian path.

Counterexample 4 There exists a conforming triangular grid with no local cut vertices and no interior vertices for which there is no through-vertex Hamiltonian cycle. See Fig. 5.

Since the inclusion of an interior vertex "fixes" Counterexample 4, a natural question is whether it can also "fix" Counterexample 3. The following counter-example says that this is not the case.

Counterexample 5 There exists a conforming triangular grid with no local cut vertices and at least one interior vertex for which there is no through-edge Hamiltonian path. See Fig. 12.

[FIGURE 10 OMITTED]

[FIGURE 11 OMITTED]

4. Quadrilaterals and Hexahedra

It is not known under what conditions any kind of Hamiltonian path or cycle is guaranteed to exist for quadrilateral and hexahedral grids, or even if there is any characterization. It would certainly be much more stringent conditions than for triangles and tetrahedra, as the following counterexample shows. By replacing the squares with cubes, the same counterexample works for hexahedral grids.

[FIGURE 12 OMITTED]

[FIGURE 13 OMITTED]

Counterexample 6 There exists a conforming quadrilateral grid with no local cut vertices and at least one interior vertex for which there is no Hamiltonian path. See Fig. 13.

The proofs of Theorems 2 and 3 break down when applied to quadrilaterals and hexahedra because, in the notation of those theorems, [E.sub.k+1] is not guaranteed to contain either the in-vertex or out-vertex of [E.sub.i]. Without that condition, it is more difficult, and in some cases impossible, to modify the cycle in a way that adds [E.sub.k+1] to it.

However, there are some other transformations of the cycle that can be applied to insert [E.sub.k+1] into the cycle in some situations. These include some situations where the grid is 1-nonconforming. Most of these transformations apply not only to quadrilaterals and hexahedra, but to any shape of element, including triangles and tetrahedra, and to mixed elements. Thus one could write a general program that applies to any grid. The illustrations will show the application of the transformations to quadrilaterals. They show examples of the transformations, but are not exhaustive.

An algorithm that attempts to find a through-vertex Hamiltonian cycle begins by picking two elements that share an edge (face in three dimensions) and constructing a cycle consisting of these two elements and two of the vertices they share. Then repeatedly pick an element that is not in the cycle but shares an edge (face in three dimensions) with an element in the cycle, and attempt to add it to the cycle by trying all of the following transformations that apply until one succeeds. If none of them succeed then try another element and come back to this one later. If there are elements not yet added to the cycle and none of the transformations work with any of the remaining elements, then you must insert a "broken link" creating a discontinuity in the path, i.e., insert an element such that either it is not adjacent to the previous or next element in the cycle, or the in-vertex and out-vertex do not match. When all elements have been added to the (possibly broken) cycle, the algorithm finishes.

In the following transformations, the cycle contains the segment [v.sub.i-2][E.sub.i-1][v.sub.i-1][E.sub.i][v.sub.i][E.sub.i+1][v.sub.i+1] and E is an element that shares an edge (face in three dimensions) with [E.sub.i] and is not in the cycle.

Transformation 1 If E contains [v.sub.i] and shares another vertex, u [not equal to] [v.sub.i-1], with [E.sub.i], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1][E.sub.i]uE[v.sub.i][E.sub.i+1][v.sub.i+1]. See Fig. 14.

This is the same transformation that was used in the proof of Theorem 2.

[FIGURE 14 OMITTED]

Transformation 2 If E contains [v.sub.i-1] and shares another vertex, u [not equal to] [v.sub.i] with [E.sub.i], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1]Eu[E.sub.i][v.sub.i][E.sub.i+1][v.sub.i-1].

This is like the previous transformation, but using the in-vertex instead of the out-vertex.

Transformation 3 If E contains both [v.sub.i-1] and [v.sub.i], and [E.sub.i-1] shares another vertex, u [not equal to] [v.sub.i-2] with [E.sub.i], then replace the segment with [v.sub.i-2][E.sub.i-1]u[E.sub.i][v.sub.i-1]E[v.sub.i][E.sub.i+1][v.sub.i+1]. See Fig. 15.

[FIGURE 15 OMITTED]

Transformation 4 If E contains both [v.sub.i-1] and [v.sub.i], and [E.sub.i+1] shares another vertex, u [not equal to] [v.sub.i+1] with [E.sub.i], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1]E[v.sub.i][E.sub.i]u[E.sub.i+1][v.sub.i+1].

This is like the previous transformation, but with the change occurring at the out-vertex of [E.sub.i] instead of the in-vertex.

Transformation 5 If E shares a vertex [u.sub.1] [not equal to] [v.sub.i] with [E.sub.i], and shares a vertex [u.sub.2] with [E.sub.i-1], [u.sub.2] [not equal to] [u.sub.1] and [u.sub.2] [not equal to] [v.sub.i-2], then replace the segment with [v.sub.i-2][E.sub.i-1][u.sub.2]E[u.sub.1][E.sub.i][v.sub.i][E.sub.i+1][v.sub.i+1]. See Fig. 16.

[FIGURE 16 OMITTED]

This transformation can also handle some forms of hanging nodes, as shown in Fig. 17.

[FIGURE 17 OMITTED]

Transformation 6 If E shares a vertex [u.sub.1] [not equal to] [v.sub.i-1] with [E.sub.i], and shares a vertex [u.sub.2] with [E.sub.i+1], [u.sub.2] [not equal to] [u.sub.1] and [u.sub.2] [not equal to] [v.sub.i+1], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1][E.sub.i][u.sub.1]E[u.sub.2] [E.sub.i+1][v.sub.i+1].

This is like the previous transformation, but with the changes occurring at [E.sub.i+1] instead of [E.sub.i-1].

Transformation 7 If E contains neither [v.sub.i-1] nor [v.sub.i], but it shares a vertex [u.sub.1] with [E.sub.i-1], [u.sub.1] [not equal to] [v.sub.i-2], and shares a vertex [u.sub.2] with [E.sub.i], [u.sub.2] [not equal to] [u.sub.1], then replace the segment with [v.sub.i-2][E.sub.i-1][u.sub.1]E[u.sub.2][E.sub.i][v.sub.i][E.sub.i+1][v.sub.i+1]. See Fig. 18.

[FIGURE 18 OMITTED]

Transformation 8 If E contains neither [v.sub.i-1] nor [v.sub.i], but it shares a vertex [u.sub.1] with [E.sub.i+1], [u.sub.1] [not equal to] [v.sub.i+1], and shares a vertex [u.sub.2] with [E.sub.i], [u.sub.2] [not equal to] [u.sub.1], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1][E.sub.i][u.sub.2]E[u.sub.1][E.sub.i+1][v.sub.i+1].

This is like the previous transformation, but with the changes occurring at [E.sub.i+1] instead of [E.sub.i-1].

Transformation 9 If E contains [v.sub.i] and there is another element, F. that is not on the cycle, shares a vertex, [u.sub.1] [not equal to] [v.sub.i], with E, and shares a vertex [u.sub.2] with [E.sub.i], [u.sub.2] [not equal to] [u.sub.1] and [u.sub.2] [not equal to] [v.sub.i-1], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1][E.sub.i][u.sub.2]F[u.sub.1]E[v.sub.i][E.sub.i+1][v.sub.i+1].

This transformation can handle some instances of hanging nodes, as shown in Fig. 19. It can also handle case 2 in the proof of Theorem 3, although it places the elements in a different order than that used in the proof.

[FIGURE 19 OMITTED]

Transformation 10 If E contains [v.sub.i-1] and there is another element, F, that is not on the cycle, shares a vertex, [u.sub.1] [not equal to] [v.sub.i-1], with E. and shares a vertex [u.sub.2] with [E.sub.i], [u.sub.2] [not equal to] [u.sub.1] and [u.sub.2] [not equal to] [v.sub.i], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1]E[u.sub.1]F[u.sub.2][E.sub.i][v.sub.i][E.sub.i+1][v.sub.i+1].

This is like the previous transformation, but with E sharing the in-vertex of [E.sub.i] instead of the out-vertex.

Transformation 11 If E contains both [v.sub.i-1] and [v.sub.i], then replace the segment with [v.sub.i-2][E.sub.i-1][v.sub.i-1]E[v.sub.i][E.sub.i+1][v.sub.i+1].

This is the swapping of one element for another that was described in case 3 of the proof of Theorem 3. One would next attempt to add [E.sub.i] back into the cycle. If done recursively, this will handle case 3b of Theorem 3.

5. Conclusion

We considered the existence of various types of Hamiltonian paths and cycles in two-dimensional grids consisting of triangles or quadrilaterals, and three-dimensional grids consisting of tetrahedra or hexahedra. The types of Hamiltonian paths and cycles are distinguished by whether passage from one element to the next must be associated with an edge (through-edge Hamiltonian), must be associated with a vertex (through-vertex Hamiltonian), or can pass through either (unconstrained Hamiltonian). The existence results presented in this paper can be summarized as:

1. There exists an unconstrained Hamiltonian path in any conforming triangular grid with no local cut vertices (previously known result). This is easily extended to Hamiltonian cycle.

2. There exist triangular grids for which there is no through-edge Hamiltonian path (previously known result). This also holds for through-face Hamiltonian paths in tetrahedral grids.

3. There exists a through-vertex Hamiltonian cycle (and hence through-vertex Hamiltonian path) for any conforming triangular grid with no local cut vertices and at least one interior vertex.

4. There exists a through-vertex Hamiltonian cycle (and hence through-vertex Hamiltonian path, unconstrained Hamiltonian cycle and unconstrained Hamiltonian path) for any tetrahedral grid that contains no local cut vertices and no local cut edges.

5. There exist rectangular grids for which there is no Hamiltonian path or cycle of any type. This also holds for hexahedral grids.

Examples were given to show that the stated conditions are essential. Some open questions remain:

1. It is not known if the absence of local cut vertices is essential for the existence of a Hamiltonian path in a triangular grid. (The absence of cut vertices is essential, and the absence of local cut vertices is essential for a Hamiltonian cycle.)

2. It is not known if the presence of an interior vertex is essential for the existence of a Hamiltonian path in a triangular grid. (It is essential for a Hamiltonian cycle.)

3. The conditions under which any type of Hamiltonian path or cycle exists in a rectangular or hexahedral grid are not known.

The existence proofs for through-vertex Hamiltonian cycles in triangular and tetrahedral grids are constructive proofs. An efficient algorithm to find such a cycle can be derived from the construction in the proofs. Another algorithm, which can be applied to elements of any shape, was outlined. This algorithm is not guaranteed to find a through-vertex Hamiltonian cycle even if one exists, but it is likely to produce a (possibly broken) cycle that is close.

Accepted: February 23, 2005

Available online: http://www.nist.gov/jres

6. References

[1] J. R. Pilkington and S. B. Baden, Dynamic partitioning of non-uniform structured workloads with spacefilling curves, IEEE Trans. on Par, and Dist. Sys. 7(3), 288-300 (1996).

[2] J. Flaherty, R. Loy, M. Shephard, B. Szymanski, J. Teresco, and L. Ziantz, Adaptive local refinement with octree load-balancing for the parallel solution of three-dimensional conservation laws, J. Parallel Distrib. Comput. 47, 139-152 (1998).

[3] W. F. Mitchell, The k-way refinement-tree partitioning method for adaptive grids, in progress.

[4] K. Devine, B. Hendrickson, E. Boman, M. St. John, C. Vaughan, and W. F. Mitchell, Zoltan: A dynamic load-balancing library for parallel applications, User's Guide, Sandia Technical Report SAND99-1377, Sandia National Laboratories, Albuquerque, NM (2000).

[5] G. Heber, R. Biswas, and G. R. Gao, Self-avoiding walks over two-dimensional adaptive unstructured grids, NAS Technical Report, NAS-98-007, NASA Ames Research Center, Moffett Field, CA (1998).

[6] U. Dogrusoz and M. S. Krishnamoorthy, Hamiltonian cycle problem for triangle graphs, Computer Science Technical Report TR95-7, Rensselaer Polytechnic Institute, Troy, NY (1995).

William F. Mitchell

National Institute of Standards and Technology, Gaithersburg, MD 20899-8910

[e-mail] 

About the author: William F. Mitchell is a computer scientist in the Mathematical and Computational Mathematics Division of the NIST Information Technology Laboratory. The National Institute of Standards and Technology is an agency of the Technology Administration, U.S. Department of Commerce.