Editing Euclidean minimum spanning tree (section)

==Realization==
The ''realization problem'' for Euclidean minimum spanning trees takes an abstract [[tree (graph theory)|tree]] as input and seeks a geometric location for each vertex of the tree (in a space of some fixed dimension), such that the given tree equals the minimum spanning tree of those points. Not every abstract tree has such a realization; for instance, the tree must obey the [[kissing number]] bound on the degree of each vertex. Additional restrictions exist; for instance, it is not possible for a planar minimum spanning tree to have a degree-six vertex adjacent to a vertex of degree five or six.{{r|monsur}} Determining whether a two-dimensional realization exists is [[NP-hard]]. However, the proof of hardness depends on the fact that degree-six vertices in a tree have a very restricted set of realizations: the neighbors of such a vertex must be placed on the vertices of a [[regular hexagon]] centered at that vertex.{{r|ew94}} Indeed, for trees of maximum degree five, a planar realization always exists.{{r|monsur}} Similarly, for trees of maximum degree ten, a three-dimensional realization always exists.{{r|king}} For these realizations, some trees may require edges of exponential length and bounding boxes of exponential area relative to the length of their shortest edge.{{r|abcfks}} Trees of maximum degree four have smaller planar realizations, with polynomially bounded edge lengths and bounding boxes.{{r|frakau}}