Polynomial area bounds for MST embeddings of trees

DOI10.1016/J.COMGEO.2011.05.005zbMATH Open1234.05068OpenAlexW2029888508MaRDI QIDQ654291FDOQ654291

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

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

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)

Cites Work

• Title not available (Why is that?)
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Computing proximity drawings of trees in the 3-dimensional space
• Small area drawings of outerplanar graphs
• Handbook of graph drawing and visualization
• A near-linear area bound for drawing binary trees
• Triangulations without minimum-weight drawing
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• The strength of weak proximity
• 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
• The rectangle of influence drawability problem
• Title not available (Why is that?)
• Polynomial Area Bounds for MST Embeddings of Trees
• The Problem of the Thirteen Spheres
• Area-efficient planar straight-line drawings of outerplanar graphs
• AREA-EFFICIENT ORDER-PRESERVING PLANAR STRAIGHT-LINE DRAWINGS OF ORDERED TREES
• Open rectangle-of-influence drawings of inner triangulated plane graphs
• Approximation schemes for degree-restricted MST and red-blue separation problems
• 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
• Computing β-Drawings of 2-Outerplane Graphs in Linear Time
• A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
• The drawability problem for minimum weight triangulations

Cited In (9)

• Drawing a tree as a minimum spanning tree approximation
• Succinct greedy drawings do not always exist
• Drawing a tree as a minimum spanning tree approximation
• 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)