We can express this problem using the notion of dilation. The dilation of a pair of vertices in an embedded planar graph is the ratio between two kinds of distance: the length of the shortest path between them in the graph, and their geometric distance. The dilation of the graph is the maximum dilation of any two of its vertices. A graph has dilation one if and only if there is a direct path between each pair of vertices. Which graphs can have dilation one?
The pattern of solutions is common to many areas of mathematics: there are several infinite families of solutions, together with a few isolated special cases. Actually, here there is exactly one special case. First, the infinite families. Note that, if there are five or more vertices in the graph, some path must have two or more edges (there is no way to find a planar embedding of a five-vertex graph in which each vertex is connected to each other by a single edge). Let P denote the path having the most vertices; then there are four infinite families:
|1. All vertices are on P:|
|2. One vertex is not on P:|
|3. Two vertices are on opposite sides of P; the path between them passes through a vertex on P:|
|4. Two vertices are on opposite sides of the line through P; the edge between them misses P:|
However, there is one more case: the graph can consist of a triangle nested inside another triangle, with three two-edge paths formed by two inner vertices and one outer vertex.
The proof that these are the only possibilities is a straightforward case analysis. If there is at most one point on either side of P, the graph is in one of the four infinite families. Otherwise, there are some two points x and y on the same side of P. If line xy passes through an endpoint of P, we can form a subset of the graph in which five points form a vee. But then, four of the points form a crossroads from which we can find a smaller vee, leading to an infinite regress. If line xy misses any vertex of P, we can form a crossroads between x, y, and two points of P, again forming a vee and an infinite regress. So, the only remaining case is that P has only three points, and that line xy passes through the middle point, forming a tee. If this is not in one of our infinite families, there must be a further point z on one side or the other of xy, and the same analysis shows that z must be one endpoint of a line through an endpoint of P and the middle point of the path containing x and y. These points together form the irregular case above, and it is not hard to see that any additional points would lead to an infinite regress.
From the Geometry Junkyard,
and recreational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.
Last update: .