TY - UNPB
T1 - Compatible Spanning Trees in Simple Drawings of Kn
AU - Aichholzer, Oswin
AU - Knorr, Kristin
AU - Mulzer, Wolfgang
AU - Maalouly, Nicolas El
AU - Obenaus, Johannes
AU - Paul, Rosna
AU - Reddy, Meghana M.
AU - Vogtenhuber, Birgit
AU - Weinberger, Alexandra
N1 - 12 pages, 6 figures, "Appears in the proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)"
PY - 2022/8/25
Y1 - 2022/8/25
N2 - For a simple drawing D of the complete graph Kn, two (plane) subdrawings are compatible if their union is plane. Let TD be the set of all plane spanning trees on D and F(TD) be the compatibility graph that has a vertex for each element in TD and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that F(TD) is connected if D is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of F(TD) 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.
AB - For a simple drawing D of the complete graph Kn, two (plane) subdrawings are compatible if their union is plane. Let TD be the set of all plane spanning trees on D and F(TD) be the compatibility graph that has a vertex for each element in TD and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that F(TD) is connected if D is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of F(TD) 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.
KW - math.CO
KW - 05C10 (Primary)
KW - G.2.2
M3 - Preprint
BT - Compatible Spanning Trees in Simple Drawings of Kn
ER -