On the area requirements of Euclidean minimum spanning trees

DOI10.1016/J.COMGEO.2012.10.011MaRDI QIDQ390122zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, Claudio Squarcella

Publication date 22 January 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://infoscience.epfl.ch/record/175657/files/Fabrizio%20Frati%20-%20On%20the%20area%20requirements%20of%20Euclidean....pdf

zbMATH Keywords

computational geometryEuclidean minimum spanning treelower boundminimum area

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the area requirements of Euclidean minimum spanning trees
• Polynomial area bounds for MST embeddings of trees
• Polynomial Area Bounds for MST Embeddings of Trees
• Drawing a tree as a minimum spanning tree approximation
• Drawing a tree as a minimum spanning tree approximation

Cites work

• Characterizing proximity trees
• Degree-bounded minimum spanning trees
• Drawing a tree as a minimum spanning tree approximation
• Euclidean bounded-degree spanning tree ratios
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On two geometric problems related to the travelling salesman problem
• Polynomial area bounds for MST embeddings of trees
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Euclidean degree-4 minimum spanning tree problem is NP-hard
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Transitions in geometric minimum spanning trees

Cited in

(10)

• The realization problem for Euclidean minimum spanning trees is NP-hard
• Euclidean bottleneck bounded-degree spanning tree ratios
• Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree
• Drawing a tree as a minimum spanning tree approximation
• Drawing a tree as a minimum spanning tree approximation
• Testing Euclidean minimum spanning trees in the plane
• On the area requirements of Euclidean minimum spanning trees
• Polynomial Area Bounds for MST Embeddings of Trees
• Drawing graphs as spanners
• Polynomial area bounds for MST embeddings of trees

This page was built for publication: On the area requirements of Euclidean minimum spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390122)