UrquhartGraph - Maple Help

GraphTheory[GeometricGraphs]

 UrquhartGraph
 construct Urquhart graph

 Calling Sequence UrquhartGraph( P, opts )

Parameters

 P - Matrix or list of lists representing set of points opts - (optional) one or more options as specified below

Options

 • triangulation = list of three-element lists.
 Supply a previously computed Delaunay triangulation of P. The input must be a valid Delaunay triangulation in the format returned by ComputationalGeometry[DelaunayTriangulation]: a list of three-element lists of integers, representing triangles in a triangulation of P.
 • vertices = list of integers, strings or symbols
 Specifies the vertices to be used in the generated graph.
 • weighted = truefalse
 If weighted=true, the result is a weighted graph whose edge weights correspond to the Euclidean distance between points. The default is false.

Description

 • The UrquhartGraph(P, opts) command returns an Urquhart graph for the point set P.
 • The parameter P must be a Matrix or list of lists representing a set of points.

Definitions

 • Let $P$ be a set of points in $n$ dimensions.
 • The Urquhart graph is the undirected graph whose vertices correspond to points in $P$ and in which an edge between $p$ and $q$ exists if $p$ and $q$ are the edge of a triangle in a Delaunay triangulation of $P$ but are not the longest of any triangle in this triangulation.
 • Intuitively, the Urquhart graph is obtained from a Delaunay triangulation by simply removing the longest edge from each triangle. It was proposed by R. B. Urquhart as an efficient method for approximating the relative neighborhood graph.
 • The Urquhart graph has the following relationships with other graphs:
 The relative neighborhood graph on P is a subgraph of the Urquhart graph on P.
 The Urquhart graph on P is a subgraph of the Gabriel graph on P.

Examples

Generate a set of random two-dimensional points and draw the Urquhart graph.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{GeometricGraphs}\right):$
 > $\mathrm{points}≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(60,2,\mathrm{generator}=0..100.,\mathrm{datatype}={\mathrm{float}}_{8}\right)$
 > $\mathrm{UG}≔\mathrm{UrquhartGraph}\left(\mathrm{points}\right)$
 ${\mathrm{UG}}{≔}{\mathrm{Graph 1: an undirected graph with 60 vertices and 65 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(\mathrm{UG}\right)$

References

 Urquhart, R. B. (1980), "Algorithms for computation of relative neighborhood graph", Electronics Letters, 16 (14): 556–557. doi:10.1049/el:19800386

Compatibility

 • The GraphTheory[GeometricGraphs][UrquhartGraph] command was introduced in Maple 2020.