Name for graph where disc connecting two points contains no other points?

Question

Hello! The problem is the following:

Given is a set of points P on a 2-dimensional plane. Each with two points (p, q) are connected by an edge, if a circle with the diameter pq exists, which does NOT contain any other points from P and if p and q are on the circumcircle. (so p and q are the ending points of the diameter of the circle)

Does anyone know what the name of this type of graph is?

Thanks for an answer and greetings from Germany!

Answer 1

Well, its definitely a planar graph because according to this definition, because there is no way two edges could be intersecting. If this happened then at least one of the end points would be contained in the circle defined by the other edges. To prove this you would probably do a proof by contradiction (assume there exists two edges e1 and e2 which intersect). Though Ill leave the proof as an exercise for the OP (because this kind of sounds like homework).

Answer 2

This is called a Gabriel graph.

I didn't know this before this question. It sounded related to the Delaunay triangulation and a little searching turned up the name pretty quickly. Interestingly, the Gabriel graph is a subgraph of the Delaunay triangulation.