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.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456