On planar path transformation

A flip or edge-replacement is considered as a transformation by which one edge e of a geometric object is removed and an edge f (f≠e) is inserted such that the resulting object belongs to the same class as the original object. Here, we consider Hamiltonian planar paths as geometric objects. A technique is presented for transforming a given planar path into another one for a set S of n points in convex position in the plane. Under these conditions, we show that any planar path can be transformed into another planar path by at most 2n−5 flips. For the case when the points are in general position we provide experimental results regarding transformability of any planar path into another. We show that for n⩽8 points in general position any two paths can be transformed into each other. For n points in convex position we show that there are n2n−2 directed Hamiltonian planar paths. An algorithm is presented which uses flips of size 1 and flips of size 2 to generate all such paths with O(n) time between the generation of two successive paths.