Exploring Increasing-Chord Paths and Trees
| Autor: | Bahoo, Yeganeh, Durocher, Stephane, Mehrpour, Sahar, Mondal, Debajyoti |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A straight-line drawing $\Gamma$ of a graph $G=(V,E)$ is a drawing of $G$ in the Euclidean plane, where every vertex in $G$ is mapped to a distinct point, and every edge in $G$ is mapped to a straight line segment between their endpoints. A path $P$ in $\Gamma$ is called increasing-chord if for every four points (not necessarily vertices) $a,b,c,d$ on $P$ in this order, the Euclidean distance between $b,c$ is at most the Euclidean distance between $a,d$. A spanning tree $T$ rooted at some vertex $r$ in $\Gamma$ is called increasing-chord if $T$ contains an increasing-chord path from $r$ to every vertex in $T$. In this paper we prove that given a vertex $r$ in a straight-line drawing $\Gamma$, it is NP-complete to determine whether $\Gamma$ contains an increasing-chord spanning tree rooted at $r$. We conjecture that finding an increasing-chord path between a pair of vertices in $\Gamma$, which is an intriguing open problem posed by Alamdari et al., is also NP-complete, and show a (non-polynomial) reduction from the 3-SAT problem. Comment: A preliminary version appeared at the 29th Canadian Conference on Computational Geometry (CCCG 2017) |
| Databáze: | arXiv |
| Externí odkaz: |
|