On the area requirements of Euclidean minimum spanning trees

DOI10.1016/j.comgeo.2012.10.011zbMath1280.05063OpenAlexW2011697681MaRDI QIDQ390122

Michael Kaufmann, Fabrizio Frati, Till Bruckdorfer, Marco Chiesa, Patrizio Angelini, 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

lower boundcomputational geometryminimum areaEuclidean minimum spanning tree

Mathematics Subject Classification ID

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

Related Items (3)

Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree ⋮ Drawing graphs as spanners ⋮ Euclidean bottleneck bounded-degree spanning tree ratios

Cites Work

• Unnamed Item
• Polynomial area bounds for MST embeddings of trees
• Degree-bounded minimum spanning trees
• Transitions in geometric minimum spanning trees
• Euclidean bounded-degree spanning tree ratios
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Characterizing proximity trees
• Drawing a Tree as a Minimum Spanning Tree Approximation
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On two geometric problems related to the travelling salesman problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• The Euclidean degree-4 minimum spanning tree problem is NP-hard

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