A note on the path graph of a set of points in convex position in the plane.
Eduardo Rivera‐Campo, Virginia Urrutia-Galicia · Canadian Conference on Computational Geometry · 1999
For any connected abstract graph G, the tree graph T (G) is the graph that has one vertex for each spanning tree of G and an edge joining trees R and S whenever R is obtained from S by a single edge exchange. R. L. Cummings proved in [C] that T (G) is hamiltonian; see also [S] for a short proof. A geometric variation that has been studied is the following: For a set P of points in general position in the plane the plane tree graph T (P ) of P is defined as the abstract graph with one vertex for each plane spanning tree of P , in which two trees are adjacent if, as in the abstract case, one is obtained from the other by a single edge exchange. D. Avis and K. Fukuda proved in [A] that G(P ) is always connected. In [H], C. Hernando et al show that if the points in P are the vertices of a convex polygon, then G(P ) is hamiltonian. In this note we only consider sets P of points in convex position and study the subgraph G (P ) of T (P ), induced by the set of plane spanning paths of P . We prove that G(P ) is itself hamiltonian. Since for any spanning path T of P planarity depends only on the relative position of its vertices along the convex hull of P , then for any set P of n points in convex position in the plane, the graph G(P ) is isomorphic to G (Pn), where Pn is a regular n-gon. We denote by Gn the graph G (Pn). The graphs G3 and G4 are shown in Figure 1. The main result of this article is the following.