Geometric tree graphs of points in convex position

Given a set P of points in the plane, the geometric tree graph of P is defi ned as the graph T(P) whose vertices are non-crossing spanning with straigh t edges trees of P, and where two trees T-1 and T-2 are adjacent if T-2 = T -1 - e + f for some edges e and f. In this paper we concentrate on the geom etric tree graph of a set of n points in convex position, denoted by G(n). We prove several results about G(n), among them the existence of Hamiltonia n cycles and the fact that they have maximum connectivity. (C) 1999 Elsevie r Science B.V. All rights reserved.