On the area requirements of Euclidean minimum spanning trees

DOI10.1016/J.COMGEO.2012.10.011zbMATH Open1280.05063OpenAlexW2011697681MaRDI QIDQ390122FDOQ390122

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

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

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)

Cites Work

• Title not available (Why is that?)
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• 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
• On two geometric problems related to the travelling salesman problem
• The Euclidean degree-4 minimum spanning tree problem is NP-hard
• Polynomial area bounds for MST embeddings of trees

Cited In (11)

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

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)