(vi) The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k. nodes of a unit disk graph and running First-Fit according to this ordering. As such, this provides a tight bound for points on a circle. (v) For every finite point set on a circle, there exists a plane (i.e., crossing-free) 4-hop spanner. Previously, no lower bound greater than 2 was known. (iv) For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. In 4, many algorithmic problems chromatic number, maximum independent set, min-imum dominating set have been proved to be NP-hard on unit disk graphs. This is the first nontrivial construction of 2-hop spanners. Notice that the class of 1-precision unit disk graphs is contained in the class of 2-precision unit disk graphs, for every 1 2. (iii) Every n-vertex unit disk graph has a 2-hop spanner with O(nlogn) edges. (ii) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. (i) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. The square G2of G is dened as a graph on the same vertex set as G and having edges between pairs of vertices with graph distance at most two in G.
We obtain the following results for unit disk graphs in the plane. A graph G is a Unit Disk (UD) graph if there is an assignment of unit disks centered at its vertices such that there is an edge in G i the corresponding unit disks intersect. A spanning subgraph G′ of G is a k-hop spanner if and only if for every edge pq∈G, there is a path between p,q in G′ with at most k edges. A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p,q∈P if and only if |pq|≤1.
0 kommentar(er)
