# What edges are not in a Gabriel graph, yet in a Delauney graph?

It is know that the Gabriel graph of a point set $$P \subset \mathbb{R}^2$$, $$\mathcal{GG}(P)$$ is a subset of the corresponding Delauney graph $$\mathcal{DG}(P)$$, i.e. $$\mathcal{GG}(P) \subseteq\mathcal{DG}(P)$$.

A Gabriel graph is defined as:

The Gabriel graph $$\mathcal{GG}(P)$$ of a point set $$P \subset \mathbb{R}^2$$ is defined as follows. The vertex set is $$P$$ and two vertices $$p, q$$ in $$P$$ are connected by an edge if and only if the interior of the disk with diameter $$\overline{pq}$$ is empty and $$p, q$$ are the only two points on its boundary. In particular, this implies that $$\overline{pq}$$ is also an edge in the Delaunay graph of P.

However, I am struggling to visualize or understand in what cases an edge $$(p, q)$$ would be in $$\mathcal{DG}(P)$$ but not in $$\mathcal{GG}(P)$$. Could someone give me an example? It seems to me as, by the empty-circle property of Voronoi edges, and their duality with the Delaunay graph, every edge in the Delaunay graph should satisfy the definition of a Gabriel graph. It is obvious that I am missing some edge case.

• Note that the smallest disk containing a triangle and the smallest disk containing an edge of this triangle are, in general, not the same. Draw a triangle, all the disks for the Gabriel graph and the disk for the Delaunay graph. Can you place a point that does not destroy the Delaunay edge, but does destroy the Gabriel edge? Dec 27, 2021 at 13:05

A Delaunay edge $$(x,y)$$ won't be a Gabriel edge, if the set of all the possible empty disks with $$x$$ and $$y$$ on their boundaries doesn't contain the disk with minimum possible radius (which is the half-length of this edge). In other words, this will happen when the Delaunay edge $$(x,y)$$ doesn't intersect the segment (or ray), separating sites $$x$$ and $$y$$ in the Voronoi diagram.