On the Stretch Factor of Randomly Embedded Random Graphs |
| |
Authors: | Abbas Mehrabian Nick Wormald |
| |
Institution: | 1. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada
|
| |
Abstract: | We consider a random graph $\mathcal{G}(n,p)$ whose vertex set $V,$ of cardinality $n,$ has been randomly embedded in the unit square and whose edges, which occur independently with probability $p,$ are given weight equal to the geometric distance between their end vertices. Then each pair $\{u,v\}$ of vertices has a distance in the weighted graph, and a Euclidean distance. The stretch factor of the embedded graph is defined as the maximum ratio of these two distances, over all $\{u,v\}\subseteq V.$ We give upper and lower bounds on the stretch factor (holding asymptotically almost surely), and show that for $p$ not too close to 0 or 1, these bounds are the best possible in a certain sense. Our results imply that the stretch factor is bounded with probability tending to 1 if and only if $n(1-p)$ tends to 0, answering a question of O’Rourke. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|