Generalized Thrackles and Geometric Graphs in ${mathbb{R}}^3$ with No Pair of Strongly Avoiding Edges

摘要

We define the notion of a geometric graph in ${mathbb{R}}^3$ . This is a graph drawn in ${mathbb{R}}^3$ with its vertices drawn as points and its edges as straight line segments connecting corresponding points. We call two disjoint edges of G strongly avoiding if there exists an orthogonal projection of $mathbb{R}^3$ to a two dimensional plane H such that the projections of the two edges on H are contained in two different rays, respectively, with a common apex that create a non-acute angle. We show that a geometric graph on n vertices in $mathbb{R}^3$ with no pair of strongly avoiding edges has at most 2n ? 2 edges. As a consequence we get a new proof to Vázsonyi’s conjecture about the maximum number of diameters in a set of n points in ${mathbb{R}}^3$ .