**Authors: **[tex2html_wrap4192]*P. Eades, S. Whitesides*

**Investigator username:** sue

**Category: ** perception

**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.

baron@cim.mcgill.ca