Triangles and Girth in Disk Graphs and Transmission Graphs Let S subset mathbbR2 be a set of n sites, where each s in S has an associated radius r_s u003e 0. The disk graph D(S) is the undirected graph with vertex set S and an undirected edge between two sites s, t in S if and only if st leq r_s  r_t, i.e., if the disks with centers s and t and respective radii r_s and r_t intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph T(S) is the directed graph with vertex set S and a directed edge from a site s to a site t if and only if st leq r_s, i.e., if t lies in the disk with center s and radius r_s.  :123,provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in D(S) and in T(S). These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in D(S) and in T(S) can be found in O(n log n) expected time, and that the (weighted) girth of D(S) can be found in O(n log n) expected time. For this, we develop new tools for batched range searching that may be of independent interest.

On the Computational Complexity of Finding Bipartite Graphs with a Small Number of Short Cycles and Large Girth The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good lowdensity paritycheck (LDPC) codes. In this paper, we prove that for a given set of integers alpha, beta, and gamma, and degree sequences pi and pixe2x80x99, the problem of determining whether there exists a simple bipartite graph with degree sequences (pi, piu0027) that has at most alpha (beta and gamma) cycles of length four (six and eight, respectively) is NPcomplete. This is proved by a twostep polynomialtime reduction from the 3Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence pi, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is pi and has a girth of at least six.