Document Open Access Logo

Shortcuts for the Circle

Authors Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Christos Levcopoulos

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.9.pdf
  • Filesize: 0.77 MB
  • 13 pages

Document Identifiers

Author Details

Sang Won Bae
Mark de Berg
Otfried Cheong
Joachim Gudmundsson
Christos Levcopoulos

Cite As Get BibTex

Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, and Christos Levcopoulos. Shortcuts for the Circle. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.9

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 + Theta(1/k^(2/3)) for any k.

Subject Classification

Keywords
  • Computational geometry
  • graph augmentation problem
  • circle
  • shortcut
  • diameter

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. W. Bae, M. de Berg, O. Cheong, J. Gudmundsson, and C. Levcopoulos. Shortcuts for the Circle, 2016. URL: http://arxiv.org/abs/1612.02412.
  2. D. Bilò, L. Gualà, and G. Proietti. Improved approximability and non-approximability results for graph diameter decreasing problems. Theoretical Computer Science, 417:12-22, 2012. Google Scholar
  3. J. Cáceres, D. Garijo, A. González, A. Márquez, M. L. Puertas, and P. Ribeiro. Shortcut sets for plane Euclidean networks (extended abstract). Electronic Notes in Discrete Mathematics, 54:163-168, 2016. URL: http://dx.doi.org/10.1016/j.endm.2016.09.029.
  4. J.-L. De Carufel, C. Grimm, A. Maheshwari, and M. Smid. Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.1.
  5. F. R. K. Chung. Diameters of graphs: old problems and new results. Congressus Numerantium, 60:295-317, 1987. Google Scholar
  6. F. R. K. Chung and M. R. Garey. Diameter bounds for altered graphs. Journal of Graph Theory, 8:511-534, 1984. Google Scholar
  7. P. Erdös and A. Rényi. On a problem in the theory of graphs (in Hungarian). Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 7:623-641, 1962. Google Scholar
  8. P. Erdös, A. Rényi, and V. T. Sós. On a problem of graph theory. Studia Scientarium Mathematicarum Hungar, 1:215-235, 1966. Google Scholar
  9. F. Frati, S. Gaspers, J. Gudmundsson, and L. Mathieson. Augmenting graphs to minimize the diameter. Algorithmica, 72(4):995-1010, 2015. Google Scholar
  10. U. Große, J. Gudmundsson, C. Knauer, M. Smid, and F. Stehn. Fast algorithms for diameter-optimally augmenting paths. In 42nd International Colloquium Automata, Languages, and Programming (ICALP), pages 678-688. Springer, 2015. Google Scholar
  11. S. Kapoor and M. Sarwat. Bounded-diameter minimum-cost graph problems. Theory of Computing Systems, 41(4):779-794, 2007. Google Scholar
  12. C. L. Li, S. T. McCormick, and D. Simchi-Levi. On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Operation Research Letters, 11(5):303-308, 1992. Google Scholar
  13. A. A. Schoone, H. L. Bodlaender, and J. van Leeuwen. Diameter increase caused by edge deletion. Journal of Graph Theory, 11:409-427, 1987. Google Scholar
  14. H. Wang. An improved algorithm for diameter-optimally augmenting paths in a metric space, 2016. URL: http://arxiv.org/abs/1608.04456.
  15. B. Yang. Euclidean chains and their shortcuts. Theoretical Computer Science, 497:55-67, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.021.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact