اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTriangles and Girth in Disk Graphs and Transmission Graphs
106
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $S subset mathbb{R}^2$ be a set of $n$ sites, where each $s in S$ has an associated radius $r_s > 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$. We 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.
قيم البحث
اقرأ أيضاً
We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$(1 + o(1)) frac{1}{3 sqrt 2} n^{3/2}.$$ We also show a connection to $r$-uniform hypergraphs without (Berge) cycles of lengt
h less than six, and estimate their maximum possible size.
Let $S$ be a set of $n$ sites, each associated with a point in $mathbb{R}^2$ and a radius $r_s$ and let $mathcal{D}(S)$ be the disk graph on $S$. We consider the problem of designing data structures that maintain the connectivity structure of $mathca
l{D}(S)$ while allowing the insertion and deletion of sites. For unit disk graphs we describe a data structure that has $O(log^2n)$ amortized update time and $O((log n)/(loglog n))$ amortized query time. For disk graphs where the ratio $Psi$ between the largest and smallest radius is bounded, we consider the decremental and the incremental case separately, in addition to the fully dynamic case. In the fully dynamic case we achieve amortized $O(Psi lambda_6(log n) log^{9}n)$ update time and $O(log n)$ query time, where $lambda_s(n)$ is the maximum length of a Davenport-Schinzel sequence of order $s$ on $n$ symbols. This improves the update time of the currently best known data structure by a factor of $Psi$ at the cost of an additional $O(log log n)$ factor in the query time. In the incremental case we manage to achieve a logarithmic dependency on $Psi$ with a data structure with $O(alpha(n))$ query and $O(logPsi lambda_6(log n) log^{9}n)$ update time. For the decremental setting we first develop a new dynamic data structure that allows us to maintain two sets $B$ and $P$ of disks, such than at a deletion of a disk from $B$ we can efficiently report all disks in $P$ that no longer intersect any disk of $B$. Having this data structure at hand, we get decremental data structures with an amortized query time of $O((log n)/(log log n))$ supporting $m$ deletions in $O((nlog^{5}n + m log^{9}n) lambda_6(log n) + nlogPsilog^4n)$ overall time for bounded radius ratio $Psi$ and $O(( nlog^{6} n + m log^{10}n) lambda_6(log n))$ for general disk graphs.
Let $P subset mathbb{R}^2$ be a planar $n$-point set such that each point $p in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q in P$, there is an edge from $
p$ to $q$ if and only if $d(p, q) leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H subseteq G$ with vertex set $P$ so that for any two vertices $p,q in P$, we have $d_H(p, q) leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (log n + log Psi))$ time, where $Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n log^5 n)$ time, independent of $Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can reach a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(log nlog Psi)$ to the query time and $O(n log Psi)$ to the space.
Bollobas and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r+1}$-free graph on at least $r+1$ vertices and $m$ edges, then $lambda^2_1(G)+lambda^2_2(G)leq frac{r-1}{r}cdot2m$, where $lambda_1(G)$
and $lambda_2(G)$ are the largest and the second largest eigenvalues of the adjacency matrix $A(G)$, respectively. In this paper, we confirm the conjecture in the case $r=2$, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to ErdH{o}s and Nosal respectively, we prove that every non-bipartite graph $G$ of order $n$ and size $m$ contains a triangle, if one of the following is true: (1) $lambda_1(G)geqsqrt{m-1}$ and $G eq C_5cup (n-5)K_1$; and (2) $lambda_1(G)geq lambda_1(S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil}))$ and $G eq S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil})$, where $S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil})$ is obtained from $K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil}$ by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.
Suppose we have an arrangement $mathcal{A}$ of $n$ geometric objects $x_1, dots, x_n subseteq mathbb{R}^2$ in the plane, with a distinguished point $p_i$ in each object $x_i$. The generalized transmission graph of $mathcal{A}$ has vertex set ${x_1, d
ots, x_n}$ and a directed edge $x_ix_j$ if and only if $p_j in x_i$. Generalized transmission graphs provide a generalized model of the connectivity in networks of directional antennas. The complexity class $exists mathbb{R}$ contains all problems that can be reduced in polynomial time to an existential sentence of the form $exists x_1, dots, x_n: phi(x_1,dots, x_n)$, where $x_1,dots, x_n$ range over $mathbb{R}$ and $phi$ is a propositional formula with signature $(+, -, cdot, 0, 1)$. The class $exists mathbb{R}$ aims to capture the complexity of the existential theory of the reals. It lies between $mathbf{NP}$ and $mathbf{PSPACE}$. Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for $exists mathbb{R}$. Continuing this line of research, we show that the recognition problem of generalized transmission graphs of line segments and of circular sectors is hard for $exists mathbb{R}$. As far as we know, this constitutes the first such result for a class of directed graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
