Polynomial area bounds for MST embeddings of trees

DOI10.1016/j.comgeo.2011.05.005zbMath1234.05068OpenAlexW2029888508MaRDI QIDQ654291

Michael Kaufmann, Fabrizio Frati

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) Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Succinct greedy drawings do not always exist ⋮ PROXIMITY DRAWINGS OF HIGH-DEGREE TREES ⋮ On the area requirements of Euclidean minimum spanning trees ⋮ Drawing graphs as spanners ⋮ The approximate rectangle of influence drawability problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangulations without minimum-weight drawing
• The strength of weak proximity
• Area-efficient planar straight-line drawings of outerplanar graphs
• Open rectangle-of-influence drawings of inner triangulated plane graphs
• Small area drawings of outerplanar graphs
• Degree-bounded minimum spanning trees
• Transitions in geometric minimum spanning trees
• The rectangle of influence drawability problem
• Euclidean bounded-degree spanning tree ratios
• Approximation schemes for degree-restricted MST and red-blue separation problems
• A near-linear area bound for drawing binary trees
• 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
• The Problem of the Thirteen Spheres
• On two geometric problems related to the travelling salesman problem
• 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
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• AREA-EFFICIENT ORDER-PRESERVING PLANAR STRAIGHT-LINE DRAWINGS OF ORDERED TREES
• Computing proximity drawings of trees in the 3-dimensional space
• On the Area Requirements of Euclidean Minimum Spanning Trees
• The Euclidean degree-4 minimum spanning tree problem is NP-hard
• Computing β-Drawings of 2-Outerplane Graphs in Linear Time
• Polynomial Area Bounds for MST Embeddings of Trees
• A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
• The drawability problem for minimum weight triangulations

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