Compatible Spanning Trees in Simple Drawings of $K_n$

Abstract

For a simple drawing $D$ of the complete graph $K_n$, two (plane) subdrawings are compatible if their union is plane. Let ${\mathcal{T}}_D$ be the set of all plane spanning trees on $D$ and $\mathcal{F}({\mathcal{T}}_D)$ be the compatibility graph that has a vertex for each element in ${\mathcal{T}}_D$ and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that $\mathcal{F}({\mathcal{T}}_D)$ is connected if $D$ is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of $\mathcal{F}({\mathcal{T}}_D)$ induced by stars, double stars, and twin stars is also connected. In all cases the diameter of the corresponding compatibility graph is at most linear in $n$.

12 pages, 6 figures, "Appears in the proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)"