Simple spanning trees in geometric graphs

Note: The talk will be given in Hebrew.

For a set P of points in the plane, the Simple Spanning Tree (SST) graph on P, denoted by G(P), is a graph whose "vertices" are simple (i.e., non-crossing) trees whose set of vertices is P, such that two trees are connected by an "edge" if their symmetric difference contains only two edges.

In this talk we would like to characterize the center of G(P). It turns out that the center of G(P) is related to the notion of a blocker for SSTs, defined as a set of edges which has at least one edge in common with any SST on P.

First, we give a complete characterization of the blockers which are smallest w.r.t. the number of edges. Concretely, we show that these are either stars (i.e., trees of diameter 2) or special structures called "caterpillars", that were first studied by Harary and Schwenk in 1971, and appear in diverse applications in graph theory.

Then we use the minimal blockers to give an almost complete characterization of the center of G(P). We show that all the elements of the center are minimal blockers, and that all the "caterpillar" minimal blockers are elements of the center. Thus, the only remaining case is the stars, for which we show that some are elements of the center, while others are not.

Based on joint works with Micha Perles, Eduardo Rivera-Campo, and Virginia Urrutia-Galicia.