Computing β-Stretch Paths in Drawings of Graphs

Authors Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, Joseph S. B. Mitchell



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.7.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Author Details

Esther M. Arkin
  • Stony Brook University, NY, USA
Faryad Darabi Sahneh
  • University of Arizona, Tucson, AZ, USA
Alon Efrat
  • University of Arizona, Tucson, AZ, USA
Fabian Frank
  • University of Arizona, Tucson, AZ, USA
Radoslav Fulek
  • University of Arizona, Tucson, AZ, USA
Stephen Kobourov
  • University of Arizona, Tucson, AZ, USA
Joseph S. B. Mitchell
  • Stony Brook University, NY, USA

Cite AsGet BibTex

Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell. Computing β-Stretch Paths in Drawings of Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SWAT.2020.7

Abstract

Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π=f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p∈P and q∈P, the length of the sub-curve of π connecting f(p) with f(q) is at most β||f(p)-f(q)‖, where ‖.‖ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. The βSP also asks that we output P if it exists. The βSP quantifies a notion of "near straightness" for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε>0, β∈O(poly(log |V(G)|)), and s,t∈V(G), outputs a β-stretch path between s and t, if a (1-ε)β-stretch path between s and t exists in the drawing.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Theory of computation → Computational geometry
Keywords
  • stretch factor
  • dilation
  • geometric spanners

Metrics

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

References

  1. Soroush Alamdari, Timothy M Chan, Elyot Grant, Anna Lubiw, and Vinayak Pathak. Self-approaching graphs. In International Symposium on Graph Drawing, pages 260-271. Springer, 2012. Google Scholar
  2. Boris Aronov, Mark De Berg, Esther Ezra, and Micha Sharir. Improved bounds for the union of locally fat objects in the plane. SIAM Journal on Computing, 43(2):543-572, 2014. Google Scholar
  3. Jonas Azzam and Raanan Schul. How to take shortcuts in Euclidean space: making a given set into a short quasi-convex set. Proceedings of the London Mathematical Society, 105(2):367-392, 2012. Google Scholar
  4. Prosenjit Bose and Michiel Smid. On plane geometric spanners: A survey and open problems. Computational Geometry, 46(7):818-830, 2013. Google Scholar
  5. Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D Tóth. On the stretch factor of polygonal chains. arXiv preprint arXiv:1906.10217, 2019. Google Scholar
  6. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28(1):210-236, 1998. Google Scholar
  7. Mark de Berg. Improved bounds on the union complexity of fat objects. Discrete & Computational Geometry, 40(1):127-140, 2008. Google Scholar
  8. Annette Ebbers-Baumann, Rolf Klein, Elmar Langetepe, and Andrzej Lingas. A fast algorithm for approximating the detour of a polygonal chain. Computational Geometry, 27(2):123-134, 2004. Google Scholar
  9. David Eppstein. Spanning trees and spanners. Handbook of computational geometry, pages 425-461, 1999. Google Scholar
  10. David Eppstein, Michael T. Goodrich, Doruk Korkmaz, and Nil Mamano. Defining equitable geographic districts in road networks via stable matching. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2017, Redondo Beach, CA, USA, November 7-10, 2017, pages 52:1-52:4, 2017. Google Scholar
  11. Mohammad Farshi, Panos Giannopoulos, and Joachim Gudmundsson. Improving the stretch factor of a geometric network by edge augmentation. SIAM Journal on Computing, 38(1):226-240, 2008. Google Scholar
  12. Christian Icking, Rolf Klein, and Elmar Langetepe. Self-approaching curves. Mathematical Proceedings of the Cambridge Philosophical Society, 125(3):441-453, 1999. Google Scholar
  13. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  14. Rolf Klein and Martin Kutz. Computing geometric minimum-dilation graphs is np-hard. In International Symposium on Graph Drawing, pages 196-207. Springer, 2006. Google Scholar
  15. Giri Narasimhan and Michiel Smid. Approximating the stretch factor of euclidean graphs. SIAM Journal on Computing, 30(3):978-989, 2000. Google Scholar
  16. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. Google Scholar
  17. David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory, 13(1):99-116, 1989. Google Scholar
  18. Daniel D. Polsby and Robert D. Popper. The third criterion: Compactness as a procedural safeguard against partisan gerrymandering. Yale Law and Policy Review, 9(2):301-353, 1991. Google Scholar
  19. Kristopher Tapp. Measuring political gerrymandering. The American Mathematical Monthly, 126(7):593-609, 2019. Google Scholar
  20. A Frank van der Stappen, Dan Halperin, and Mark H Overmars. The complexity of the free space for a robot moving amidst fat obstacles. Computational Geometry, 3(6):353-373, 1993. Google Scholar
  21. A Frank van der Stappen and Mark H Overmars. Motion planning amidst fat obstacles. In Proceedings of the tenth annual symposium on Computational geometry, pages 31-40. ACM, 1994. Google Scholar
  22. Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. Google Scholar
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