Asymptotically Optimal Solutions for Small World Graphs