Next: Drawing Graphs in Up: Geometric Algorithms Previous: Geometric Algorithms

The Realization Problem for Euclidean Minimum Spanning Trees is NP-hard

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.