Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees

Abstract Let P be a set of n points in the plane, no three in a line. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the crossing type (for short, x-type) of P specifies, for every unordered pair of line segments spanned by P, whether they cross each other. Keller and Perles (2016) proved that the x-type of P can be reconstructed from the exchange graph G 0 ( P ) of noncrossing spanning trees. In this paper, we show that the x-type of P can already be reconstructed from the compatible exchange graph G 1 ( P ) , which is a subgraph of G 0 ( P ) . The proof crucially relies on the analysis of maximal sets of pairwise noncrossing edges ( m snes) between two disjoint planar straight-line graphs. m snes are a bipartite analogue of triangulations of planar straight-line graphs; they correspond to maximal cliques in G 1 ( P ) .