The realization problem for Euclidean minimum spanning trees is NP-hard

DOI10.1007/BF02086608zbMath0851.68084OpenAlexW2073262840MaRDI QIDQ1920421

Peter Eades, S. H. Whitesides

Publication date: 10 November 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02086608

zbMATH Keywords

NP-hardEuclidean minimum spanning tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges, Proximity drawings in polynomial area and volume, The logic engine and the realization problem for nearest neighbor graphs, PROXIMITY DRAWINGS OF HIGH-DEGREE TREES, The strength of weak proximity, On nearest-neighbor graphs, The rectangle of influence drawability problem, On the area requirements of Euclidean minimum spanning trees, Nearest neighbour graph realizability is NP-hard, 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, Complexity results for three-dimensional orthogonal graph drawing, Complexity dichotomy on partial grid recognition, The drawability problem for minimum weight triangulations, Polynomial Area Bounds for MST Embeddings of Trees, Voronoi drawings of trees

Cites Work

• Realizability of Delaunay triangulations
• Layouts with wires of balanced length
• The complexity of minimizing wire lengths in VLSI layouts
• Unit-length embedding of binary trees on a square grid
• The complexity of drawing trees nicely
• Transitions in geometric minimum spanning trees
• A note on optimal area algorithms for upward drawings of binary trees
• Characterizing proximity trees
• TWO TREE DRAWING CONVENTIONS
• NP-completeness for minimizing maximum edge length in grid embeddings
• Pretty-printing of trees
• Universality considerations in VLSI circuits
• PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA
• Unnamed Item
• Unnamed Item