Estimating shortest paths in planar drawings of graphs

Question

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!

Answer 1

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.

Answer 2

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.