The unit disk graph (UDG) is a widely employed model for the study of wireless networks. In this model, wireless nodes are represented by points in the plane and there is an edge between two points if and only if their Euclidean distance is at most one. A hop spanner for the UDG is a spanning subgraph @math such that for every edge @math in the UDG the topological shortest path between @math and @math in @math has a constant number of edges. The hop stretch factor of @math is the maximum number of edges of these paths. A hop spanner is plane (i.e. embedded planar) if its edges do not cross each other. The problem of constructing hop spanners for the UDG has received considerable attention in both computational geometry and wireless ad hoc networks. Despite this attention, there has not been significant progress on getting hop spanners that (i) are plane, and (ii) have low hop stretch factor. Previous constructions either do not ensure the planarity or have high hop stretch factor. The only construction that satisfies both conditions is due to Catusse, Chepoi, and Vax e s (2010); their plane hop spanner has hop stretch factor at most 449. Our main result is a simple algorithm that constructs a plane hop spanner for the UDG. In addition to the simplicity, the hop stretch factor of the constructed spanner is at most 341. Even though the algorithm itself is simple, its analysis is rather involved. Several results on the plane geometry are established in the course of the proof. These results are of independent interest.
To the best of our knowledge, the only construction that guarantees the planarity of the entire hop spanner is due to Catusse, Chepoi, and Vax e s @cite_7 . First they use a regular square-grid to partition input points into clusters. Then they add edges between points in different clusters, and also between points in the same cluster to obtain a hop spanner, which is not necessarily plane. Then they go through several steps and in each step they remove some edges to ensure planarity, and add some new edges to maintain constant hop stretch factor. At the end they obtain a plane hop spanner with hop stretch factor at most @math . This spanner can be obtained by a localized distributed algorithm.
@cite_7
1766136887
The simplest model of a wireless network graph is the Unit Disk Graph (UDG): an edge exists in UDG if the Euclidean distance between its endpoints is ≤ 1. The problem of constructing planar spanners of Unit Disk Graphs with respect to the Euclidean distance has received considerable attention from researchers in computational geometry and ad-hoc wireless networks. In this paper, we present an algorithm that, given a set X of terminals in the plane, constructs a planar hop spanner with constant stretch factor for the Unit Disk Graph defined by X. Our algorithm improves on previous constructions in the sense that (i) it ensures the planarity of the whole spanner while previous algorithms ensure only the planarity of a backbone subgraph; (ii) the hop stretch factor of our spanner is significantly smaller.