There are planar graphs almost as good as the complete graph

摘要

Given a set S of points in the plane, the complete graph on S (the graph with an edge connecting each pair of points) is the only graph with the property that for any points A and B of S there exists an A-to-B path along edges of the graph with path length equal to the straight-line distance between A and B. We show there is a planar graph G on S with a similar property: for any points A and B of S, there exists an A-to-B path along edges of G with path length at most 2 |AB|, where |AB| is the Euclidean straight-line distance between A and B. If S is of size n then, because G is planar, G has just O(n) edges instead of the O(n2) edges required for the complete graph. The graph G that has this property is a type of Delaunay triangulation. Applications include network design and motion planning.