---
OA_place: publisher
OA_type: gold
_id: '18556'
abstract:
- lang: eng
text: 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.
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.
alternative_title:
- LIPIcs
article_number: '3'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Ondrej
full_name: Draganov, Ondrej
id: 2B23F01E-F248-11E8-B48F-1D18A9856A87
last_name: Draganov
orcid: 0000-0003-0464-3823
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: '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'
apa: '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'
chicago: 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.
ieee: 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.
ista: '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.'
mla: 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.
short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, in:,
32nd International Symposium on Graph Drawing and Network Visualization, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-20
location: Vienna, Austria
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2024-09-18
corr_author: '1'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-28T00:00:00Z
date_updated: 2025-12-02T13:50:50Z
day: '28'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.GD.2024.3
ec_funded: 1
external_id:
arxiv:
- '2403.10204'
isi:
- '001540278400001'
file:
- access_level: open_access
checksum: 5f9b35e115c3d375e99be78da9054cb4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T07:49:25Z
date_updated: 2024-11-18T07:49:25Z
file_id: '18560'
file_name: 2024_LIPIcs_CultreradiMontesano.pdf
file_size: 908541
relation: main_file
success: 1
file_date_updated: 2024-11-18T07:49:25Z
has_accepted_license: '1'
intvolume: ' 320'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: 32nd International Symposium on Graph Drawing and Network Visualization
publication_identifier:
isbn:
- '9783959773430'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Euclidean MST-ratio for bi-colored lattices
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 320
year: '2024'
...