Contents

-

Finding Longest Cycles in Inner-Triangulated Graphs

Robert J.Cimikowski1
1Computer Science Department Montana State University Bozeman, Montana 59717-0388 U.S.A.

Abstract

We examine the problem of finding longest cycles in inner triangulations, that is, 2-connected planar graphs in which all interior faces are triangles. These include the important family of geometric graphs called Delaunay triangulations In particular, we present two efficient heuristics for finding a longest cycle in an inner triangulation. The heuristics operate by considering at each step a local set of faces adjacent to the current cycle as candidates for inclusion in the cycle.