# Estimating shortest paths in planar drawings of graphs

Consider a drawing (in $$\mathbb{R}^2$$) of a planar graph. (The drawing is given, contrarily to the common setup in graph theory where we are seeking to build a drawing with specific properties.)

For two vertices $$u$$ and $$v$$ of the graph let us call the edge distance between $$u$$ and $$v$$ the length of the shortest path only following edges connecting $$u$$ and $$v$$. In other words, it is the shortest path in the graph weighted by the edge lengths.

I am interested in any general results/references that could apply to this (seemingly, natural?) notion. More specifically, I am interested in results applicable to triangulations and convex drawings.

To narrow the scope of the question, let me showcase it by an example of a specific problem:

Consider a triangulated square with side $$1$$ in $$\mathbb{R}^2$$. The triangulation is geometric, i.e. it is drawn in $$\mathbb{R}^2$$, with straight edges and without self-intersections. It can have extra vertices in the interior of the square, but, for simplicity, let it not have extra vertices on the sides (in other words, the original square sides are edges of the triangulation).

Is it true that, for any vertex of the triangulation, it is at an edge distance of less than $$1$$ from at least one of the square vertices?

Thank you!

• Just to aid you in searching for results: What you call a drawing of the graph is usually called an embedding of the graph in the plane. A graph with edge lengths is generally called a metric graph. Another closely related topic is quantum graph which are metric graphs plus specified boundary conditions on the vertices for a Laplace type of operator on the graph. Commented May 21 at 5:56
• @quarague Thank you! Knowing the correct lingo for an area helps tremendously. Commented May 21 at 14:16

Here are triangulations of a side $$1$$ square with vertices at a arbitrarily high distance of all the four vertices of the square. The sides of the side $$1$$ square are not edges but it is easy to see that that can be avoided.

Let $$k\in\mathbb{N}$$; we consider a $$4k$$-gon $$K_0$$ inscribed in the square; we can construct a sequence $$(K_n)_n$$ of $$4k$$-gons such that the vertices of $$K_n$$ are the midpoints of consecutive vertices of $$K_{n-1}$$. In the picture below we show a few of the $$16$$-gons $$K_n$$ in the case $$k=4$$.

Our graph $$G$$ will consist on the square, the polygons $$K_n$$ for $$n=1,\dots,N$$ (where $$N$$ is big) and some triangulations of $$K_N$$ and the regions between the square and $$K_0$$.

Note that the radius of $$K_{n+1}$$ is the radius of $$K_n$$ times $$\cos\left(\frac{\pi}{4k}\right)$$. Thus, the side of $$K_n$$ is $$l_k\cdot\cos\left(\frac{\pi}{4k}\right)^n$$, where $$l_k>\frac{1}{4k}$$ is the side of $$K_0$$.

Any edge path from a vertex of the square to a vertex of $$K_N$$ must traverse at least half an edge of the polygons $$K_0,\dots,K_{N-1}$$. Thus, it will have length at least $$\frac{1}{2}\sum_{n=0}^{N-1}l_k\cdot\cos\left(\frac{\pi}{4k}\right)^n$$. When $$N\to\infty$$, this expression becomes

$$\frac{1}{2}l_k\frac{1}{1-\cos\left(\frac{\pi}{4k}\right)}\geq \frac{1}{2}\frac{1}{4k}\frac{1}{\left(\frac{\pi}{4k}\right)^2}=\frac{2k}{\pi^2}.$$

Thus, if we want to obtain a vertex at distance at least some constant $$L$$ from the four vertices of the square, we just need to take $$k$$ such that $$\frac{2k}{\pi^2}>L$$ and let $$N$$ be big enough.

• besides the extra edge vertices, this also has several non-triangular regions; fortunately they are easily triangulated. One easy way to remove the extra edge vertices is to start with K_3 and connect each of its vertices to the nearest corner(s) of the square. Commented May 21 at 4:49
• (Also, as it stands this is not a topological triangulation because each triangle's long side has a vertex at its midpoint. Possibly the OP is fine with that. If not, it can be fixed by replacing each such side with an epsilon-thin triangle, as I did in my construction which is the special case k=1.) Commented May 21 at 5:30
• @NoamD.Elkies In the answer I mention that the graph includes triangulations of the non-triangular regions (this clearly does not affect the bounds I give on edge distances). I also considered what you say in your second comment, but from the statement of the question it didn't seem to me like it was prohibited that two edges form an angle of $\pi$ at a vertex (as he remarks that he does not want this to hold specifically for the sides of the square). But as you say, this can be easily fixed if necessary Commented May 21 at 10:45
• Thank you! I really like the idea, especially for the following reason: it is not so much about the square, as it presents a general way to build graphs with embeddings with (Euclidean) close subgraphs, but arbitrarily far from each other edge-wise by separating them with your "annulus" construction. Commented May 21 at 14:28

Looks like Saúl RM has already achieved an arbitrarily high distance.
Here's a simpler construction that at least gets distance $$> 1$$.

The square has vertices $$(\pm1/2, \pm1/2)$$. The vertices near the square have coordinates $$(0,\pm(1/2 - \epsilon))$$ and $$(\pm(1/2 - \epsilon), 0)$$ The shaded inner square has vertices $$(\pm(1/4 - \epsilon), \pm(1/4 - \epsilon))$$. Each vertex of the inner square is at edge distance $$(2+\sqrt2)/4 - O(\epsilon)$$ from the nearest corners of the outer square.

Thus we attain a center-to-corner distance of $$\frac12 (1+\sqrt2) - O(\epsilon) > 1.2$$ by simply connecting each of the inner square's vertices to the center, dividing it into four isosceles right triangles. Even better to iterate the construction, subdividing the inner square in the same way into 12 more triangles and a square of side $$(\frac12 - 2\epsilon)^2$$, and then subdividing that square, etc., finally connecting each vertex of the innermost square to the center. That comes arbitrarily close to $(2 + \sqrt2) / 2 > 1.7. • Nice. This would be an extremely simple example if the sides of the square were not required to be edges (similarly as in my construction, which would get more complicated if I had let the sides of the square be edges) Commented May 21 at 3:28 • Nice example, especially considering the iteration. Thank you! I will note Saul's answer as correct because of the slightly higher generality: one can also see your example (and the iterated one) as a slight modification of Saul's example for$k=1\$ avoiding vertices being midpoints. Commented May 21 at 14:30
• Do you happen to know if there are some essential structural results/references about problems on shortest paths/just metric geometry on graphs in the plane? I know of combinatorial results such as Sperner's or Tucker's lemmas, but they do not seem to be helpful in estimating distances, only establishing existence of paths with some non-metric properties. Essentially, I have a plethora of problems around the topic that I am trying to solve (motivated by some Riemannian geometry questions), and I do not expect a counter-example to be readily available in most cases. Commented May 21 at 14:41