  The vertex-random graphs called proximity catch digraphs (PCDs) have been
introduced recently and have applications in pattern recognition and spatial
pattern analysis. A PCD is a random directed graph (i.e., digraph) which is
constructed from data using the relative positions of the points from various
classes. Different PCDs result from different definitions of the proximity
region associated with each data point. We consider the underlying and
reflexivity graphs based on a family of PCDs which is determined by a family of
parameterized proximity maps called proportional-edge (PE) proximity map. The
graph invariant we investigate is the relative edge density of the underlying
and reflexivity graphs. We demonstrate that, properly scaled, relative edge
density of these graphs is a $U$-statistic, and hence obtain the asymptotic
normality of the relative edge density for data from any distribution that
satisfies mild regulatory conditions. By detailed probabilistic and geometric
calculations, we compute the explicit form of the asymptotic normal
distribution for uniform data on a bounded region in the usual Euclidean plane.
We also compare the relative edge densities of the two types of the graphs and
the relative arc density of the PE-PCDs. The approach presented here is also
valid for data in higher dimensions.
