Shortcuts for the Circle

Abstract

Let $C$ be the unit circle in ${\mathbb{R}}^2$. We can view $C$ as a plane graph whose vertices are all the points on $C$, and the distance between any two points on $C$ is the length of the smaller arc between them. We consider a graph augmentation problem on $C$, where we want to place $k\ge 1$ \emph{shortcuts} on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1\le k\le 7$ what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of~$k$. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is $2+\Theta (1/k^{\frac{2}{3}})$ for any~$k$.

An extended abstract appeared in ISAAC 2017