Urquhart graph

In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation.

The Urquhart graph was described by Urquhart (1980), who suggested that removing the longest edge from each Delaunay triangle would be a fast way of constructing the relative neighborhood graph (the graph connecting pairs of points

, the same time bound holds for the Urquhart graph as well.

[3] The problem of constructing relative neighborhood graphs in

time, left open by the mismatch between the Urquhart graph and the relative neighborhood graph, was solved by Supowit (1983).