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
2011 (English)In: Algorithms and Data Structures: 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, Springer Berlin/Heidelberg, 2011, Vol. 6844, p. 25-36Conference paper, Published paper (Refereed)
Abstract [en]

In their seminal paper on Euclidean minimum spanning trees [Discrete & Computational Geometry, 1992], Monma and Suri 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 c(n) x c(n) area is sometimes required to embed an n-vertex tree of maximum degree 5 as a Euclidean minimum spanning tree, 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
Springer Berlin/Heidelberg, 2011. Vol. 6844, p. 25-36
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6844
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222337DOI: 10.1007/978-3-642-22300-6_3ISI: 000306442500003Scopus ID: 2-s2.0-80052132931ISBN: 978-3-642-22299-3 (print)OAI: oai:DiVA.org:kth-222337DiVA, id: diva2:1180750
Conference
12th International Symposium on Algorithms and Data Structures, WADS 2011, New York, NY, United States, 15 August 2011 through 17 August 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
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 0 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