Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph

Let $P$ be a finite set of points in general position in the plane. The structure of the complete graph $K(P)$ as a geometric graph includes, for any pair $[a,b],[c,d]$ of vertex-disjoint edges, the information whether they cross or not.

 

The simple (i.e., non-crossing) spanning trees (SSTs) of $K(P)$ are the vertices of the so-called Geometric Tree Graph of $P$, $G(P)$. Two such vertices are adjacent in $G(P)$ if they differ in exactly two edges, i.e., if one can be obtained from the other by deleting an edge and adding another edge. Introduced by Avis and Fukuda in 1993, geometric tree graphs were studied in a number of papers and play an important role in algorithms for spanning trees enumeration.

 

In this talk we show how to reconstruct from $G(P)$ (regarded as an abstract graph) the structure of $K(P)$ as a geometric graph. This result can be viewed as a geometric counterpart of a work of Sedlacek (1974) on reconstruction of an abstract graph from the list of its spanning trees, and may shed light on the structure of the automorphism group of $G(P)$ whose determination is a 15-years old open problem.

 

Joint work with Micha A. Perles.

 

Note: The talk will be given in Hebrew.