Finding Longest Cycles in Inner-Triangulated Graphs

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.