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

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开发者_StackOverflow ending points of the diameter of the circle)

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

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.

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).