The Euclidean MST-ratio for bi-colored lattices
Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LIPIcs, vol. 320, 3.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
Grant
Series Title
LIPIcs
Abstract
Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25.
Publishing Year
Date Published
2024-10-28
Proceedings Title
32nd International Symposium on Graph Drawing and Network Visualization
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Acknowledgement
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, "Discretization in Geometry and Dynamics", Austrian Science Fund (FWF), grant no. I 02979-N35.
Volume
320
Article Number
3
Conference
GD: Graph Drawing and Network Visualization
Conference Location
Vienna, Austria
Conference Date
2024-09-18 – 2024-09-20
ISBN
ISSN
IST-REx-ID
Cite this
Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. The Euclidean MST-ratio for bi-colored lattices. In: 32nd International Symposium on Graph Drawing and Network Visualization. Vol 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.GD.2024.3
Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2024). The Euclidean MST-ratio for bi-colored lattices. In 32nd International Symposium on Graph Drawing and Network Visualization (Vol. 320). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.3
Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “The Euclidean MST-Ratio for Bi-Colored Lattices.” In 32nd International Symposium on Graph Drawing and Network Visualization, Vol. 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.GD.2024.3.
S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “The Euclidean MST-ratio for bi-colored lattices,” in 32nd International Symposium on Graph Drawing and Network Visualization, Vienna, Austria, 2024, vol. 320.
Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LIPIcs, vol. 320, 3.
Cultrera di Montesano, Sebastiano, et al. “The Euclidean MST-Ratio for Bi-Colored Lattices.” 32nd International Symposium on Graph Drawing and Network Visualization, vol. 320, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.GD.2024.3.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2024_LIPIcs_CultreradiMontesano.pdf
908.54 KB
Access Level
Open Access
Date Uploaded
2024-11-18
MD5 Checksum
5f9b35e115c3d375e99be78da9054cb4
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2403.10204
Google Scholar
ISBN Search