Related Graphs
The relative neighborhood graph is an example of a lens-based beta skeleton. It is a subgraph of the Delaunay triangulation. In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.
The Urquhart graph, the graph formed by removing the longest edge from every triangle in the Delaunay triangulation, was originally proposed as a fast method to compute the relative neighborhood graph. Although the Urquhart graph sometimes differs from the relative neighborhood graph it can be used as an approximation to the relative neighborhood graph.
Read more about this topic: Relative Neighborhood Graph
Famous quotes containing the word related:
“A parent who from his own childhood experience is convinced of the value of fairy tales will have no difficulty in answering his child’s questions; but an adult who thinks these tales are only a bunch of lies had better not try telling them; he won’t be able to related them in a way which would enrich the child’s life.”
—Bruno Bettelheim (20th century)