License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.7
URN: urn:nbn:de:0030-drops-122540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12254/
Arkin, Esther M. ;
Sahneh, Faryad Darabi ;
Efrat, Alon ;
Frank, Fabian ;
Fulek, Radoslav ;
Kobourov, Stephen ;
Mitchell, Joseph S. B.
Computing β-Stretch Paths in Drawings of Graphs
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.
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:1--7:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-150-4},
ISSN = {1868-8969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12254},
URN = {urn:nbn:de:0030-drops-122540},
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 |
