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 convex if it lies outside of the convex hull of its neighbors. 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 convex. 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.
翻译:几何图是在平面上绘制的图表, 以便其顶部和边缘分别以一般位置和直线段的点表示。 几何图的顶点如果位于其周围的锥体外, 则称为锥形。 我们显示, 对于带有 $ odices 和 $e 边缘的几何图来说, 至少有 $\ frac{ n ⁇ 2\\ ⁇ binom{ 2 e/ n ⁇ 3} 的两对断裂边缘, 前提是 $ 2\ geq n$ 和 图形的所有顶点都是锥体。 此外, 我们证明, 如果带有 $ $ 的 odice 的几何图形边缘与大多数 $ 的边缘脱节, 那么这个图形的边缘数不会超过 $n( sqrt{1+8m3) / 4 4, 前提是 $ 美元足够大。 这些结果对于一个无限的图形组来说是十分紧凑的 。