Computing β-Stretch Paths in Drawings of Graphs

Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen G. Kobourov, Joseph S. B. MitchellSwat 2020 · DOI

TL;DR

This paper introduces and analyzes the "β-stretch path problem" (BSP), which seeks paths in a graph drawing that are "nearly straight" by bounding the ratio of path length to Euclidean distance. The authors prove BSP is strongly NP-complete but provide a quasi-polynomial time algorithm for finding approximate β-stretch paths, offering a new way to quantify and measure "straightness" in geometric graphs with potential applications in areas like fair geographic partitioning.

What Problem Does This Paper Address?

Imagine you have a map where roads are drawn as curves, not just straight lines. Sometimes, these roads might meander significantly, making a direct trip much longer than the straight-line distance between two points. This paper tackles the problem of quantifying and finding "straight" paths in such drawings. Specifically, they define a β-stretch path as a path where the distance along the path between any two points is at most β times the direct Euclidean distance between those points. This concept is motivated by real-world problems like gerrymandering, where "natural" or "un-gerrymandered" districts might correspond to paths with low stretch. The core challenge is to determine if such a path exists between two given points in a graph drawing and, if so, to find it.

Methods

The authors introduce the formal definition of a β-stretch path and a related concept, the β-stretch cycle. They then prove that the β-stretch path problem (BSP) is strongly NP-complete by reducing it from the vertex cover problem. This means that finding an exact β-stretch path is likely computationally intractable for large graphs.

However, to provide a practical solution, they develop a quasi-polynomial time approximation scheme (QPTAS). This algorithm doesn't guarantee finding an exact β-stretch path but can find a path that is a (1-ε)β-stretch path if a β(1-ε)-stretch path exists. The QPTAS relies on a path filtering scheme that iteratively prunes sets of paths that are "equivalent" with respect to stretched radial grids. This filtering process significantly reduces the search space, allowing for a quasi-polynomial time solution. They also extend these results to the β-stretch cycle problem (BCP), showing a connection between β-stretch cycles and locally "fat" shapes.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and complexity for abstract graph drawings.

Key Insights and Ideas

  • Quantifying "Straightness": The β-stretch metric provides a precise, multiplicative way to measure how "straight" a path is, going beyond simple Euclidean distance.
  • NP-Completeness and Approximation: The problem is computationally hard (strongly NP-complete), but a practical solution is achievable through approximation algorithms. The QPTAS demonstrates that good solutions can be found efficiently even if exact solutions are not.
  • Radial Grids for Path Equivalence: The use of radial grids centered at vertices is a novel way to define path equivalence. Paths that behave similarly with respect to these grids can be pruned, significantly speeding up the search.
  • Connection to Geometric Shapes: The concept of β-stretch cycles is shown to be related to the "fatness" of geometric shapes, suggesting applications in analyzing and partitioning regions.

Key Results

  • The β-stretch path problem (BSP) is strongly NP-complete.
  • A quasi-polynomial time approximation scheme (QPTAS) is provided for BSP, which finds a β(1-ε)-stretch path if a β(1-ε)-stretch path exists.
  • A similar QPTAS is developed for the β-stretch cycle problem (BCP).
  • A β-stretch cycle is shown to bound a locally γ-fat shape, with the fatness parameter depending on β. However, the converse is not true: a locally fat shape's boundary might not be a β-stretch cycle.

Limitations and Future Work

  • NP-Hardness with Large β: The NP-hardness proof uses a construction that results in large β values (polynomial in the number of vertices). An open problem is to determine the complexity of BSP for constant or logarithmic β.
  • Drawing Assumptions: The algorithms assume edges are curves of constant algebraic complexity and that the graph drawing is "generic" with respect to the radial grids.
  • Future Directions:
    • Investigating BSP for smaller β values.
  • Developing algorithms for drawings where vertices lie on an integer grid and edges are straight-line segments.
  • Applying β-stretch paths/cycles to problems like fair geographic partitioning and defining "natural" districts that avoid gerrymandering.
  • Exploring the use of β-stretch cycles for partitioning regions such that each region contains exactly one "important" vertex.

Summary updated

BibTeX
@inproceedings{arkin2020computing,
  author = {Esther M. Arkin and Faryad Darabi Sahneh and Alon Efrat and Fabian Frank and Radoslav Fulek and Stephen G. Kobourov and Joseph S. B. Mitchell},
  title = {{Computing β-Stretch Paths in Drawings of Graphs}},
  booktitle = {Swat},
  year = {2020},
  doi = {10.4230/lipics.swat.2020.7},
}

Loading related content...

Figure