There is a planar graph almost as good as the complete graph

TLDR

For any set of planar points, a triangulation exists in which paths are at most a constant factor longer than the straight-line distance. The study aims to apply this triangulation property to motion planning in the plane. The authors employ the L1 metric Delaunay triangulation and an O(n)-size data structure to approximate shortest paths in O(n log n) time. The triangulation guarantees that any two points can be connected by a path no longer than √10 times their Euclidean distance, i.e., roughly three times the straight-line distance.

Abstract

Given a set S of points in the plane, there is a triangulation of S such that a path found within this triangulation has length bounded by a constant times the straight-line distance between the endpoints of the path. Specifically, for any two points a and b of S there is a path along edges of the triangulation with length less than √10 times |ab|, where |ab| is the straight-line Euclidean distance between a and b. Thus, a shortest path in this planar graph is less than about 3 times longer than the corresponding straight-line distance. The triangulation that has this property is the L1 metric Delaunay triangulation for the set 5. This result can be applied to motion planning in the plane. Given a source, a destination, and a set of polygonal obstacles of size n, an Ο(n) size data structure can be used to find a reasonable approximation to the shortest path between the source and the destination in Ο(n log n) time.