Paper Info
Title
Planar tree transformation: Results and counterexample
Abstract
We consider the problem of planar spanning tree transformation in a two-dimensional plane. Given two planar trees T"1 and T"2 drawn on a set S of n points in general position in the plane, the problem is to transform T"1 into T"2 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 (fe) 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,s0) 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 |T"1@?T"2|=k then they cannot be transformed to one another by k flips.
Year
DOI
Venue
2008
10.1016/j.ipl.2008.09.005
Inf. Process. Lett.
Keywords
Field
DocType
convex position,transformation result,planar tree,geometric object,original object,tree transformation,planar tree transformation,general position,resulting object,direct approach,transformation,computational geometry,spanning tree
Discrete mathematics,Direct method,Combinatorics,General position,Enumeration,Computational geometry,Planar,Spanning tree,Counterexample,Convex position,Mathematics
Journal
Volume
Issue
ISSN
109
1
0020-0190
Citations 
PageRank 
References 
2
0.39
9
Authors
3
Name
Order
Citations
PageRank
Selim G. Akl12074299.32
Kamrul Islam2767.75
Henk Meijer3753100.25