Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds---with vanishing error terms---hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
In contrast, properties of other proximity graphs of random point sets have been studied extensively: Devroye @cite_15 presents a general theorem for obtaining exact leading constants for the expected degree of a number of proximity graphs over point sets drawn from a large class of distributions. This theorem can be applied to Gabriel graphs, relative neighbourhood graphs, and nearest-neighbour graphs. This work [Section 7] devroye:expected also mentions directional nearest-neighbour graphs,'' now commonly known as Yao graphs @cite_5 @cite_11 , and points out that the general theorem does not apply to these (nor does it apply to theta graphs---for the same reasons).
@cite_5 @cite_15 @cite_11
2023618719 2051522939 2031671531
Abstract We consider n independent points with a common but arbitrary density f in R d . Two points ( X i , X j ) are joined by an edge when a certain set S ( X i , X j ) does not contain any other data points. The expected number E ( N ) of edges in the graph depends upon n , f and the definition of S . Examples include rectangle, spheres and loons; these lead to the graph of all dominance pairs, the Gabriel graph and the relative neighborhood graph, respectively. Other graphs covered by our analysis include the nearest neighbor graph and the directional nearest neighbor graph. In all cases, we obtain asymptotic lower bounds that do not depend upon f (and are hence useful in all applications involving these graphs, since we usually do not know f ). For sparse graphs, exact asymptotic constants are obtained for E ( N ) that are valid for all densities. We study an evolving spatial network in which sequentially arriving vertices are joined to existing vertices at random according to a rule that combines preference according to degree with preference according to spatial proximity. We investigate phase transitions in graph structure as the relative weighting of these two components of the attachment rule is varied. Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence of the resulting graph coincides with that of the standard Barab 'asi--Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence coincides with that of a purely geometric model, the on-line nearest-neighbour graph, which is of interest in its own right and for which we prove some extensions of known results. We also show the presence of an intermediate regime, in which the behaviour differs significantly from both the on-line nearest-neighbour graph and the Barab 'asi--Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence. Our results lend some mathematical support to simulation studies of Manna and Sen, while proving that the power law to stretched exponential phase transition occurs at a different point from the one conjectured by those authors. Suppose we are given a bipartite graph with vertex set X, Y, |X| = n , |Y| = N , each point in X (Y) has degree D(d) fixed, respectively, moreover, each pair of points x, x' ∈ X has at most D (log n) 3 (common) neighbours. Let t (X, Y) denote the minimum number of vertices of Y needed to cover all vertices of X. We prove (Theorem 1.1) that t (X, Y) d n tends to 1 as n tends to infinity. This result has many applications: Theorem [5]. Suppose k > r > 1 are fixed, n → ∞. Then there exists a collection of (1 + o (1)) × ( n r ) ( k r ) k -subsets of an n -set so that each r -subset is contained in at least one member of the collection. Analogues and strengthenings of this result are deduced. E.g. for vector spaces, orthogonal or simplectic geometries, random collections of k -sets with constant probabilities, etc. Theorem 3.3. Suppose G is a graph on v vertices and e edges and ℛ is a random graph on n vertices and edge probability e ( v 2 ). Then there exists a collection of (1 + o (1))( n 2 ) ( v 2 ) induced subgraphs of ℛ on v vertices, isomorphic to G and such that each edge (non-edge) of ℛ is covered by an edge (non-edge) of a graph in the collection. Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximum degree of a random Gabriel graph or Yao graph defined on n points drawn uniformly at random from a unit square grows as ?(log n log log n) in probability.