DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.3

The Euclidean MST-Ratio for Bi-Colored Lattices

Authors: Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

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.

Cite as

Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. The Euclidean MST-Ratio for Bi-Colored Lattices. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cultreradimontesano_et_al:LIPIcs.GD.2024.3,
  author =	{Cultrera di Montesano, Sebastiano and Draganov, Ond\v{r}ej and Edelsbrunner, Herbert and Saghafian, Morteza},
  title =	{{The Euclidean MST-Ratio for Bi-Colored Lattices}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.3},
  URN =		{urn:nbn:de:0030-drops-212878},
  doi =		{10.4230/LIPIcs.GD.2024.3},
  annote =	{Keywords: Minimum spanning Trees, Steiner Ratio, Lattices, Partitions}
}

Search Results

Documents authored by Draganov, Ondřej

The Euclidean MST-Ratio for Bi-Colored Lattices

Abstract

Cite as

Thanks for your feedback!

Could not send message