Planar tree transformation: Results and counterexample

We consider the problem of planar spanning tree transformation in a two-dimensional plane. Given two planar trees T1 and T2 drawn on a set S of n points in general position in the plane, the problem is to transform T1 into T2 by a sequence of simple changes called edge-flips or just flips. A flip is an operation 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. We present two algorithms for planar tree transformations. The first technique is an indirect approach which relies on some ‘canonical’ tree to obtain such transformation results. It is shown that it takes at most 2n−m−s−2 flips (m,s>0) which is an improvement over the result in [D. Avis, K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics 65 (1996) 21–46]. Second, we present a direct approach which takes at most n−1+k flips (k⩾0) for such transformation when S in convex position and also show results when the points are in general position. We provide cases where the second technique performs an optimal number of flips. A counterexample is given to show that if |T1∖T2|=k then they cannot be transformed to one another by k flips.