Vertex-Adjacency Dual

## Introduction## Algorithm## Applet## Bibliography |
## Introduction## The ProblemGiven any triangulation T of a set of points, how can we
arrange these triangles in a cycle C such that two triangles are consecutive
in C if and only if they share either an ## What is a Hamiltonian Cycle?A Hamiltonian cycle is a walk in a graph G that starts from
a vertex The Hamiltonian cycle is a special case of the
Traveling Salesman Problem (known as the The problem of finding a Hamiltonian cycle in an arbitrary graph is NP-complete [1].
## A Word on TriangulationsSuppose we are given a set of points edges)
in such a way that the resulting structure is a collection of triangles
joined along edges, then this set of triangles is called the triangulation
of (figure 2). A set of points P
can have many different triangulations. Similarly, a Ppolygon triangulation
is the subdivision of a polygon into a set of non-overlapping triangles
by inserting edges between pairs of vertices.
The
A Hamiltonian triangulation) is a triangulation whose
dual graph is a path (figure 4). Determining whether a polygon (with holes)
can have a serpentine triangulation is also NP-complete
[3]. A triangulation is a serpentine
triangulation with the additional property that the triangles alternate
left-right (figure 6). sequential
## Some HistoryThe problem of finding a Hamiltonian cycle in the dual graph of triangulations has been studied extensively throughout the literature. Various results that construct a Hamiltonian cycle in a given triangulation can be classified based on the model considered. In the first model, the given triangulation is allowed to
be modified by adding new vertices or In the second model, the input triangulation cannot be modified.
In this case, the problem is that of visiting adjacent triangles in some
order such that the resulting graph contains a Hamiltonian cycle. An important
property here is how Hamiltonian cycles in triangulations are studied when adjacency
is defined as In [7], a triangulation is represented with a for each triangle-vertex
and an edge v whenever (v, f)
is a vertex of triangle v. A ffacet cycle
is defined by a walk (v_{0}, f_{1}, v_{1}, f_{2},
v_{2}, ..., f_{k}, v_{k}, f_{0}, v_{0})
where no arc is repeated and that includes each facet vertex exactly once,
but may repeat triangle vertices. The authors prove that any triangulation
has a facet cycle if it is not a checkered polygonal triangulation
- that is if it does not have a 2-coloring
of the triangles such that every white triangle is adjacent to
three black ones (figure 5). This means that we can find a Hamiltonian
cycle in a polygonal triangulation of triangles,
if a 2-coloring of the triangles produces less than n
white triangles with 3 adjacent black ones (figure 5). n
A similar result under the same facet cycle model is found in [4]. Here,
Bartholdi III and Goldsman refer to general triangulation as In [6], Chen, Grigni and Papadimitriou define the Bartholdi III and Goldsman [5] introduce the same concept of a map graph
that they call the In the Algorithm section of this page, we will describe Bartholdi and
Goldsman's algorithm for constructing a Hamiltonian cycle in a general
triangulation and show how it works with an interactive Java Applet. |

This page was prepared by Perouz Taslakian - December 2004