Authors: [tex2html_wrap4192]P. Eades, S. Whitesides
Investigator username: sue
Subcategory: geometric algorithms
Given a set S of points in the plane, a spanning tree of S is a tree whose vertex set is S. The weight of such a spanning tree is the sum of the lengths of its edges. A spanning tree T of S is a minimum spanning tree of S provided that its weight is equal to or less than the weight of any other minimum spanning tree of S.
Given a combinatorial tree T = (V,E), the Minimum Spanning Tree Realizability problem (MSTR) is to determine whether T is isomorphic to a minimum spanning tree of some point set S in the plane. In this paper, we prove that MSTR is NP-hard.