2026-07-25T06:45:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12254 2024-03-06T10:49:27Z ddc:004 open_access

Computing β-Stretch Paths in Drawings of Graphs Arkin, Esther M. Sahneh, Faryad Darabi Efrat, Alon Frank, Fabian Fulek, Radoslav Kobourov, Stephen Mitchell, Joseph S. B. stretch factor dilation geometric spanners 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther M. Arkin and Faryad Darabi Sahneh and Alon Efrat and Fabian Frank and Radoslav Fulek and Stephen Kobourov and Joseph S. B. Mitchell 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.7 urn:nbn:de:0030-drops-122540 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.7 eng https://creativecommons.org/licenses/by/3.0/legalcode