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.
As discussed in the introduction, a plethora of literature exists on theta graphs and their applications, though most of this work focuses on worst-case analysis. One notable exception is the work of Devroye al @cite_17 who study the maximum degree of theta graphs and show that, if @math is a set of @math points independently and uniformly distributed in a certain unit square, then @math has maximum degree concentrated around @math . Devroye al actually consider the closely-related Yao graphs @cite_5 @cite_11 , but their proofs apply, almost without modification, to theta graphs.
@cite_5 @cite_11 @cite_17
2033513442 2590395400 2272045681 2950908404
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. We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph @math with @math vertices, and define (for @math ) @math . Our aim is to estimate @math within a multiplicative error of @math (for a given approximation parameter @math ) in sublinear time. We consider the sparse graph model that allows access to: uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of @math (the average degree), @math queries suffice for any constant @math (Feige, SICOMP 06 and Goldreich-Ron, RSA 08). Gonen-Ron-Shavitt (SIDMA 11) extended this result to all integral @math , by designing an algorithms that performs @math queries. We design a new, significantly simpler algorithm for this problem. In the worst-case, it exactly matches the bounds of Gonen-Ron-Shavitt, and has a much simpler proof. More importantly, the running time of this algorithm is connected to the degeneracy of @math . This is (essentially) the maximum density of an induced subgraph. For the family of graphs with degeneracy at most @math , it has a query complexity of @math . Thus, for the class of bounded degeneracy graphs (which includes all minor closed families and preferential attachment graphs), we can estimate the average degree in @math queries, and can estimate the variance of the degree distribution in @math queries. This is a major improvement over the previous worst-case bounds. Our key insight is in designing an estimator for @math that has low variance when @math does not have large dense subgraphs. We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d log d) approximation due to Halperin. It is also known that no o(d log2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results: (i) The natural LP formulation for the problem strengthened by O(log4(d)) levels of the mixed-hierarchy has an integrality gap of O(d log2 d), where O(·) ignores some log log d factors. However, our proof is non-constructive, in particular it uses an entropy based approach due to Shearer, and does not give a O(d log2 d) approximation algorithm with sub-exponential running time. (ii) We give an O(d log d) approximation based on polylog(d)-levels of the mixed hierarchy that runs in nO(1) exp(logO(1) d) time, improving upon Halperin's bound by a modest log log d factor. Our algorithm is based on combining Halperin's approach together with an idea used by Ajtai, Erdos, Komlos and Szemeredi to show that Kr-free, degree-d graphs have independent sets of size Ωr(n log log d d). We consider the maximum independent set problem on graphs with maximum degree @math . We show that the integrality gap of the Lov 'asz @math -function based SDP is @math . This improves on the previous best result of @math , and almost matches the integrality gap of @math recently shown for stronger SDPs, namely those obtained using poly- @math levels of the @math semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of @math -free graphs for large values of @math . We also show how to obtain an algorithmic version of the above-mentioned @math -based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of @math matches the best unique-games-based hardness result up to lower-order poly- @math factors.