Euclidean Minimum Spanning Tree - Planar Realization

Planar Realization

The realization problem for Euclidean minimum spanning trees is stated as follows: Given a tree T = (V, E), find a location D(u) for each vertex u ∈ V so that T is a minimum spanning tree of D(u): u ∈ V, or determine that no such locations exist. Testing of the existence of a realization in the plane is NP-hard.

Read more about this topic:  Euclidean Minimum Spanning Tree

Famous quotes containing the word realization:

    “The ground for taking ignorance to be restrictive of freedom is that it causes people to make choices which they would not have made if they had seen what the realization of their choices involved.”
    —A.J. (Alfred Jules)