Abstract
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1dimensional 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 (nonselfintersecting) curve, and for every pair of distinct points p∈P and q∈P, the length of the subcurve 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 NPcomplete. We complement this result by giving a quasipolynomial 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.
BibTeX  Entry
@InProceedings{arkin_et_al:LIPIcs:2020:12254,
author = {Esther M. Arkin and Faryad Darabi Sahneh and Alon Efrat and Fabian Frank and Radoslav Fulek and Stephen Kobourov and Joseph S. B. Mitchell},
title = {{Computing βStretch Paths in Drawings of Graphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {7:17:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12254},
URN = {urn:nbn:de:0030drops122540},
doi = {10.4230/LIPIcs.SWAT.2020.7},
annote = {Keywords: stretch factor, dilation, geometric spanners}
}
Keywords: 

stretch factor, dilation, geometric spanners 
Collection: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) 
Issue Date: 

2020 
Date of publication: 

12.06.2020 