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

Seminar
Speaker
Chaya Keller (Hebrew University)
Date
04/01/2015 - 15:30 - 14:00Add to Calendar 2015-01-04 14:00:00 2015-01-04 15:30:00 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.   Building 216, Room 201 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Building 216, Room 201
Abstract
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.
 

Last Updated Date : 30/12/2014