Editing Euclidean minimum spanning tree (section)

===Supergraphs===
Certain [[geometric graph]]s have definitions involving empty regions in point sets, from which it follows that they contain every edge that can be part of a Euclidean minimum spanning tree. These include:
*The [[relative neighborhood graph]], which has an edge between any pair of points whenever the lens they define is empty.
*The [[Gabriel graph]], which has an edge between any pair of points whenever the circle having the pair as a diameter is empty.
*The [[Delaunay triangulation]], which has an edge between any pair of points whenever there exists an empty circle having the pair as a chord.
*The [[Urquhart graph]], formed from the Delaunay triangulation by removing the longest edge of each triangle. For each remaining edge, the vertices of the Delaunay triangles that use that edge cannot lie within the empty lune of the relative neighborhood graph.
Because the empty-region criteria for these graphs are progressively weaker, these graphs form an ordered sequence of subgraphs. That is, using "⊆" to denote the subset relationship among their edges, these graphs have the relations:
{{bi|left=1.6|Euclidean minimum spanning tree ⊆ relative neighborhood graph ⊆ Urquhart graph ⊆ Gabriel graph ⊆ Delaunay triangulation.{{r|presha|comment}}}}
Another graph guaranteed to contain the minimum spanning tree is the [[Yao graph]], determined for points in the plane by dividing the plane around each point into six 60° wedges and connecting each point to the nearest neighbor in each wedge. The resulting graph contains the relative neighborhood graph, because two vertices with an empty lens must be the nearest neighbors to each other in their wedges. As with many of the other geometric graphs above, this definition can be generalized to higher dimensions, and (unlike the Delaunay triangulation) its generalizations always include a linear number of edges.{{r|yao82|bwy}}