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:
“No being exists or can exist which is not related to space in some way. God is everywhere, created minds are somewhere, and body is in the space that it occupies; and whatever is neither everywhere nor anywhere does not exist. And hence it follows that space is an effect arising from the first existence of being, because when any being is postulated, space is postulated.”
—Isaac Newton (1642–1727)