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 geometrylower boundEuclidean minimum spanning treeminimum area

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• 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
• Drawing a tree as a minimum spanning tree approximation
• On the area requirements of Euclidean minimum spanning trees
• Drawing a tree as a minimum spanning tree approximation
• Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree
• Polynomial Area Bounds for MST Embeddings of Trees
• Polynomial area bounds for MST embeddings of trees
• Testing Euclidean minimum spanning trees in the plane
• Euclidean bottleneck bounded-degree spanning tree ratios
• Drawing graphs as spanners

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)