Suppose, there is a square region of length L in the 2-d plane. N points are chosen from inside the region uniformly randomly. Consider these N points as the vertices (nodes) of a graph (network). There will be an edge (link) connecting two vertices if the Euclidean distance between those two corresponding points is not greater than a predefined threshold, say R. Can we get a relation among 'L', 'N', and 'R' such that the underlying graph becomes connected every time we choose the points? If not, then suppose we fix 'L' and 'N'. In this case, can we get a lower bound for 'R' such that the graph is connected?
Graphs of this type are called unit disk graphs. This may help you find what you are looking for
In an L by L square region, the Euclidean distance between any two vertices is < L * sqrt(2), assuming the vertices are in the interior of the region. So if you set R >= L * sqrt(2), you can guarantee the graph on the N vertices will be connected, as this will be the complete graph on the N vertices.
If you are looking to minimize R, in theory R could be infinitesimal, of course. However, I think the solution here would be to find a minimum spanning tree of the graph. A minimum spanning tree is necessarily a minimum bottleneck spanning tree, where...
"I... a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree."
Minimum bottleneck spanning tree - Wikipedia
So finding a minimum spanning tree for the graph should minimize R, i.e., the maximum weighted edge in the graph.
So basically you would construct the complete graph on the N vertices and assign the Euclidean distance between every pair of vertices as the edge weight. Then you would find the minimal spanning tree of this graph, which would necessarily minimize the maximum edge weight of all the edges of the graph. In other words, this would find the minimum largest Euclidean distance between two vertices necessary to keep the graph connected, and then you would set R to this, as every edge can then have weight
Dear Gourab Kumar Sar,
I'm agree With Adam Letchford that unit disk graphs is a solution for your problem also I suggest you to see links and attached file on topic.
https://drops.dagstuhl.de/opus/volltexte/2020/13360/pdf/LIPIcs-ISAAC-2020-16.pdf
Preprint Parameterized Study of Steiner Tree on Unit Disk Graphs
Book Distributed Control of Robotic Networks: A Mathematical Appr...
Best regards
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs