Polynomial area bounds for MST embeddings of trees

DOI10.1016/J.COMGEO.2011.05.005MaRDI QIDQ654291zbMATH OpenOpenAlexFDO

Authors Fabrizio Frati, Michael Kaufmann

Publication date 28 December 2011

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2011.05.005

zbMATH Keywords

minimum spanning treesarea boundsgeometric embedding

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Polynomial Area Bounds for MST Embeddings of Trees
• On the area requirements of Euclidean minimum spanning trees
• On the area requirements of Euclidean minimum spanning 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?)
• scientific article; zbMATH DE number 1500691 (Why is no real title available?)
• A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
• A near-linear area bound for drawing binary trees
• AREA-EFFICIENT ORDER-PRESERVING PLANAR STRAIGHT-LINE DRAWINGS OF ORDERED TREES
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Area-efficient planar straight-line drawings of outerplanar graphs
• Characterizing proximity trees
• Computing proximity drawings of trees in the 3-dimensional space
• Computing β-Drawings of 2-Outerplane Graphs in Linear Time
• 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
• Handbook of graph drawing and visualization
• ON MINIMUM AREA PLANAR UPWARD DRAWINGS OF DIRECTED TREES AND OTHER FAMILIES OF DIRECTED ACYCLIC GRAPHS
• On Open Rectangle-of-Influence Drawings of Planar Graphs
• On the area requirements of Euclidean minimum spanning trees
• On two geometric problems related to the travelling salesman problem
• Open rectangle-of-influence drawings of inner triangulated plane graphs
• Polynomial Area Bounds for MST Embeddings of Trees
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Small area drawings of outerplanar graphs
• The Euclidean degree-4 minimum spanning tree problem is NP-hard
• The Problem of the Thirteen Spheres
• The drawability problem for minimum weight triangulations
• The realization problem for Euclidean minimum spanning trees is NP-hard
• The rectangle of influence drawability problem
• The strength of weak proximity
• Transitions in geometric minimum spanning trees
• Triangulations without minimum-weight drawing

Cited in

(9)

• Drawing a tree as a minimum spanning tree approximation
• Drawing a tree as a minimum spanning tree approximation
• Succinct greedy drawings do not always exist
• Polynomial Area Bounds for MST Embeddings of Trees
• The approximate rectangle of influence drawability problem
• Drawing graphs as spanners
• On the area requirements of Euclidean minimum spanning trees
• Proximity drawings of high-degree trees
• On the area requirements of Euclidean minimum spanning trees

This page was built for publication: Polynomial area bounds for MST embeddings of trees

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