Disjoint edges in geometric graphs

A geometric graph is a graph drawn in the plane so that its vertices and edges are represented by points in general position and straight line segments, respectively. A vertex of a geometric graph is called pointed if it lies outside of the convex hull of its neighbours. We show that for a geometric graph with $n$ vertices and $e$ edges there are at least $\frac{n}{2}\binom{2e/n}{3}$ pairs of disjoint edges provided that $2e\geq n$ and all the vertices of the graph are pointed. Besides, we prove that if any edge of a geometric graph with $n$ vertices is disjoint from at most $m$ edges, then the number of edges of this graph does not exceed $n(\sqrt{1+8m}+3)/4$ provided that $n$ is sufficiently large. These two results are tight for an infinite family of graphs.

No reviews yet.

No comments yet.