arXiv
Open Access
2022
Shooting Stars in Simple Drawings of $K_{m,n}$
Oswin Aichholzer
Alfredo García
Irene Parada
Birgit Vogtenhuber
Alexandra Weinberger
Abstrak
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 $K_{m,n}$ contains a plane spanning tree as a subdrawing. We answer this question to the positive by showing that for every simple drawing of $K_{m,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$.
Penulis (5)
O
Oswin Aichholzer
A
Alfredo García
I
Irene Parada
B
Birgit Vogtenhuber
A
Alexandra Weinberger
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2022
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓