Hamiltonian Cycles in the
Vertex-Adjacency Dual

 

 

Introduction

Algorithm

Applet

Bibliography

Introduction

The Problem

Given 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 edge or a vertex in the given triangulation T.

What is a Hamiltonian Cycle?

A Hamiltonian cycle is a walk in a graph G that starts from a vertex v of G and ends at v after visiting all the vertices of G exactly once. It is named after William Rowan Hamilton who invented a game called icosian game - also known as Hamilton's puzzle - which involved finding a Hamiltonian cycle in the edge graph of a dodecahedron.

The Hamiltonian cycle is a special case of the Traveling Salesman Problem (known as the TSP problem), where given a number of cities and the costs of travelling from one to the other, a salesman needs to find the cheapest roundtrip route that visits each city and returns to the starting point.

The problem of finding a Hamiltonian cycle in an arbitrary graph is NP-complete [1].

Fig 1 : The cycle a - b - e - c - d - f - g is Hamiltonian

 

A Word on Triangulations

Suppose we are given a set of points P in the plane. If we connect these points with straight lines (called 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 P (figure 2). A set of points P can have many different triangulations. Similarly, a polygon triangulation is the subdivision of a polygon into a set of non-overlapping triangles by inserting edges between pairs of vertices.

Fig 2 : A triangulation of a set of points P

The dual graph of a triangulation is obtained by defining a vertex for each triangle and drawing an edge between two traingles which share an edge (figure 3). The problem of finding a Hamiltonian cycle in the dual graph of a point-set triangulation is also known to be NP-complete [2].

Fig 3 : The dual graph of a triangulation of P

A serpentine triangulation (also known and 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 sequential triangulation is a serpentine triangulation with the additional property that the triangles alternate left-right (figure 6).

Fig 4 : A serpentine triangulation and its dual graph

 

Fig 5 : A sequential triangulation and its dual graph

 

Some History

The 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 Steiner points. In [9], Gopi and Eppstein present an algorithm for constructing a Hamiltonian cycle in a given triangulation by inserting Steiner points within existing triangles. They use a dual graph matching algorithm to partition the triangulation into cycles, and then merge these cycles by splitting triangles when necessary.

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 adjacency is defined. In the dual graph of a triangulation, adjacency is defined as edge-adjacency where the dual vertices of two triangles are connected by an edge when these triangles share an edge. Unfortunately, it is not always possible to find Hamiltonian cycles in the dual graph.

Hamiltonian cycles in triangulations are studied when adjacency is defined as vertex-adjacency, where two triangles are considered to be adjacent if they share exactly at least one vertex.

In [7], a triangulation is represented with a vertex-facet incidence graph which has a vertex f for each facet (triangle), a vertex v for each triangle-vertex and an edge (v, f) whenever v is a vertex of triangle f. A facet cycle is defined by a walk (v0, f1, v1, f2, v2, ..., fk, vk, f0, v0) 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 n triangles, if a 2-coloring of the triangles produces less than n white triangles with 3 adjacent black ones (figure 5).

Fig 5 : A checkered triangulation and a vertex-facet incidence graph

 

A similar result under the same facet cycle model is found in [4]. Here, Bartholdi III and Goldsman refer to general triangulation as Triangulated Irregular Networks (TINs). The authors describe an algorithm to construct a cycle in a 2-adjacent TIN (a triangulation in which each triangle shares an edge with at least two other triangles). Their algorithm runs in O(n2) time in the worst case.

In [6], Chen, Grigni and Papadimitriou define the map graph of a planar subdivision P (or a map) to be a graph G where the vertices of G correspond to the faces of P and two vertices u and v are adjacent if their corresponding faces in P share any point on their boundary. This characterization is equivalent to the dual graph of a triangulation in which two vertices u and v of the dual are connected by an edge whenever the triangles corresponding to u and v share a triangular edge or a triangular vertex. Chen et al. study sparsity and coloring of map graphs.

Bartholdi III and Goldsman [5] introduce the same concept of a map graph that they call the vertex-adjacency dual of a general triangulation. The authors show that the vertex-adjacency dual contains a Hamiltonian cycle, and they describe a linear time algorithm to construct such a cycle. Here we note that the model described in [5] is a variation of the facet-cycle model described in [7]: In the facet cycle model a continuous walk enters every triangle from a vertex v and leaves from a different vertex u. In the vertex-adjacency dual model, u and v are allowed to be the same vertex.

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