Shooting Stars in Simple Drawings of Km , n

Oswin Aichholzer; Alfredo García; Irene Parada; Birgit Vogtenhuber; Alexandra Weinberger

doi:10.1007/978-3-031-22203-0_5

Shooting Stars in Simple Drawings of K_m _, _n

Oswin Aichholzer, Alfredo García, Irene Parada^*, Birgit Vogtenhuber, Alexandra Weinberger

^*Corresponding author for this work

Institute of Software Technology (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

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.

Original language	English
Title of host publication	Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
Editors	Patrizio Angelini, Reinhard von Hanxleden
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	49-57
Number of pages	9
ISBN (Print)	9783031222023
DOIs	https://doi.org/10.1007/978-3-031-22203-0_5
Publication status	Published - 2023
Event	30th International Symposium on Graph Drawing and Network Visualization: GD 2022 - Tokyo, Japan Duration: 13 Sept 2022 → 16 Jan 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13764 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	30th International Symposium on Graph Drawing and Network Visualization
Abbreviated title	GD 2022
Country/Territory	Japan
City	Tokyo
Period	13/09/22 → 16/01/23

Keywords

Complete bipartite graph
Plane spanning tree
Shooting star
Simple drawing
Simple topological graph

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-22203-0_5

Cite this

Aichholzer, O., García, A., Parada, I., Vogtenhuber, B., & Weinberger, A. (2023). Shooting Stars in Simple Drawings of K_m _, _n. In P. Angelini, & R. von Hanxleden (Eds.), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers (pp. 49-57). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13764 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-22203-0_5

Shooting Stars in Simple Drawings of K_m _, _n. / Aichholzer, Oswin; García, Alfredo; Parada, Irene et al.
Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. ed. / Patrizio Angelini; Reinhard von Hanxleden. Springer Science and Business Media Deutschland GmbH, 2023. p. 49-57 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13764 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Aichholzer, O, García, A, Parada, I, Vogtenhuber, B & Weinberger, A 2023, Shooting Stars in Simple Drawings of K_m _, _n. in P Angelini & R von Hanxleden (eds), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13764 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 49-57, 30th International Symposium on Graph Drawing and Network Visualization, Tokyo, Japan, 13/09/22. https://doi.org/10.1007/978-3-031-22203-0_5

Aichholzer O, García A, Parada I, Vogtenhuber B, Weinberger A. Shooting Stars in Simple Drawings of K_m _, _n. In Angelini P, von Hanxleden R, editors, Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2023. p. 49-57. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-22203-0_5

Aichholzer, Oswin ; García, Alfredo ; Parada, Irene et al. / Shooting Stars in Simple Drawings of K_m _, _n. Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. editor / Patrizio Angelini ; Reinhard von Hanxleden. Springer Science and Business Media Deutschland GmbH, 2023. pp. 49-57 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9b8cea8ec8c74797a58eef78b5908b8d,

title = "Shooting Stars in Simple Drawings of Km , n",

abstract = "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.",

keywords = "Complete bipartite graph, Plane spanning tree, Shooting star, Simple drawing, Simple topological graph",

author = "Oswin Aichholzer and Alfredo Garc{\'i}a and Irene Parada and Birgit Vogtenhuber and Alexandra Weinberger",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 30th International Symposium on Graph Drawing and Network Visualization : GD 2022, GD 2022 ; Conference date: 13-09-2022 Through 16-01-2023",

year = "2023",

doi = "10.1007/978-3-031-22203-0_5",

language = "English",

isbn = "9783031222023",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "49--57",

editor = "Patrizio Angelini and {von Hanxleden}, Reinhard",

booktitle = "Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers",

address = "Germany",

}

TY - GEN

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

PY - 2023

Y1 - 2023

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 - Complete bipartite graph

KW - Plane spanning tree

KW - Shooting star

KW - Simple drawing

KW - Simple topological graph

UR - http://www.scopus.com/inward/record.url?scp=85148692283&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-22203-0_5

DO - 10.1007/978-3-031-22203-0_5

M3 - Conference paper

AN - SCOPUS:85148692283

SN - 9783031222023

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 57

BT - Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers

A2 - Angelini, Patrizio

A2 - von Hanxleden, Reinhard

PB - Springer Science and Business Media Deutschland GmbH

T2 - 30th International Symposium on Graph Drawing and Network Visualization

Y2 - 13 September 2022 through 16 January 2023

ER -

Shooting Stars in Simple Drawings of Km , n