Online Help

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.

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.

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.

$\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}\left[8\right]\right)$

$\mathrm{points}≔\begin{array}{c}\left[\begin{array}{cc}9.85017697341803& 82.9750304386195\\ 86.0670183749663& 83.3188659363996\\ 64.3746795546741& 73.8671607639673\\ 57.3670557294666& 2.34399775883031\\ 23.6234264844933& 52.6873367387328\\ 47.0027547350003& 22.2459488367552\\ 74.9213491558963& 62.0471820220718\\ 92.1513434709073& 96.3107262637080\\ 48.2319624355944& 63.7563267144141\\ 90.9441877431805& 33.8527464913022\\ ⋮& ⋮\end{array}\right]\\ \text{60 × 2 Matrix}\end{array}$

$\mathrm{UG}≔\mathrm{UrquhartGraph}\left(\mathrm{points}\right)$

$\mathrm{UG}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 60\; vertices\; and\; 65\; edges}$

$\mathrm{DrawGraph}\left(\mathrm{UG}\right)$

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

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

For more information on Maple 2020 changes, see Updates in Maple 2020 .