TY - UNPB
T1 - Shooting Stars in Simple Drawings of Km,n
AU - Aichholzer, Oswin
AU - García, Alfredo
AU - Parada, Irene
AU - Vogtenhuber, Birgit
AU - Weinberger, Alexandra
N1 - Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)
PY - 2022/9/2
Y1 - 2022/9/2
N2 - Simple drawings are drawings of graphs in which two edges have at most one common point (either a common endpoint, or a proper crossing). It has been an open question whether every simple drawing of a complete bipartite graph Km,n contains a plane spanning tree as a subdrawing. We answer this question to the positive by showing that for every simple drawing of Km,n and for every vertex v in that drawing, the drawing contains a shooting star rooted at v, that is, a plane spanning tree containing all edges incident to v.
AB - Simple drawings are drawings of graphs in which two edges have at most one common point (either a common endpoint, or a proper crossing). It has been an open question whether every simple drawing of a complete bipartite graph Km,n contains a plane spanning tree as a subdrawing. We answer this question to the positive by showing that for every simple drawing of Km,n and for every vertex v in that drawing, the drawing contains a shooting star rooted at v, that is, a plane spanning tree containing all edges incident to v.
KW - cs.CG
KW - math.CO
U2 - 10.48550/arXiv.2209.01190
DO - 10.48550/arXiv.2209.01190
M3 - Preprint
BT - Shooting Stars in Simple Drawings of Km,n
PB - arXiv
ER -