Combinatorics Seminar - Rosna Paul (Graz University of Technology)

16:15-18:00

Speaker: Rosna Paul (Graz University of Technology)

Title: Compatibility Graph of Spanning trees in Simple Drawings

Abstract: For a simple drawing D of the complete graph K_n, two
(plane) subdrawings are compatible if their union is plane. Let T_D be
the set of all plane spanning trees on D and F(T_D) be the compatibility
graph that has a vertex for each element in T_D and two vertices are
adjacent if and only if the corresponding trees are compatible. In this
talk, we will show that F(T_D) is connected if D is a 2-page book,
monotone,
or strongly c-monotone drawing. On the other hand, we also focus on the
subgraph of F(T_D) induced by stars, double stars, and twin stars and show
that this subgraph will also be connected. This is a joint work with Oswin
Aichholzer, Kristin Knorr, Wolfgang Mulzer, Nicolas El Maalouly, Johannes
Obenaus, Meghana M. Reddy, Birgit Vogtenhuber, and Alexandra Weinberger.