### Abstract

Let C be the unit circle in 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⩾1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1⩽k⩽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+Θ([formula presented]) for any k.

Original language | English |
---|---|

Pages (from-to) | 37-54 |

Number of pages | 18 |

Journal | Computational Geometry |

Volume | 79 |

DOIs | |

Publication status | Published - 1 Feb 2019 |

### Fingerprint

### Keywords

- Geometric network
- Graph augmentation
- Graph diameter

### Cite this

*Computational Geometry*,

*79*, 37-54. https://doi.org/10.1016/j.comgeo.2019.01.006

}

*Computational Geometry*, vol. 79, pp. 37-54. https://doi.org/10.1016/j.comgeo.2019.01.006

**Shortcuts for the circle.** / Bae, Sang Won; de Berg, Mark; Cheong, Otfried (Corresponding author); Gudmundsson, Joachim; Levcopoulos, Christos.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Shortcuts for the circle

AU - Bae, Sang Won

AU - de Berg, Mark

AU - Cheong, Otfried

AU - Gudmundsson, Joachim

AU - Levcopoulos, Christos

PY - 2019/2/1

Y1 - 2019/2/1

N2 - Let C be the unit circle in 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⩾1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1⩽k⩽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+Θ([formula presented]) for any k.

AB - Let C be the unit circle in 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⩾1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1⩽k⩽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+Θ([formula presented]) for any k.

KW - Geometric network

KW - Graph augmentation

KW - Graph diameter

UR - http://www.scopus.com/inward/record.url?scp=85060736146&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2019.01.006

DO - 10.1016/j.comgeo.2019.01.006

M3 - Article

AN - SCOPUS:85060736146

VL - 79

SP - 37

EP - 54

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -