Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the area requirements of Euclidean minimum spanning trees
Roma Tre University, Italy.ORCID iD: 0000-0002-9675-9729
Show others and affiliations
2014 (English)In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 47, no 2, p. 200-213Article in journal (Refereed) Published
Abstract [en]

In their seminal paper on Euclidean minimum spanning trees, Monma and Suri (1992) proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that there exist n-vertex trees of maximum degree 5 that require c(n) x c(n) area to be embedded as Euclidean minimum spanning trees, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.

Place, publisher, year, edition, pages
Elsevier, 2014. Vol. 47, no 2, p. 200-213
Keywords [en]
Euclidean minimum spanning tree, Minimum area, Lower bound, Computational geometry
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222332DOI: 10.1016/j.comgeo.2012.10.011ISI: 000330084500002Scopus ID: 2-s2.0-84887420759OAI: oai:DiVA.org:kth-222332DiVA, id: diva2:1180760
Conference
12th International Symposium on Algorithms and Data Structures (WADS), New York Univ, Polytechn Inst, New York, NY, Aug 15-17, 2011
Note

QC 20180207

Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2018-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Chiesa, Marco
In the same journal
Computational geometry
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 14 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf