2017/02/27 by Yeganeh Bahoo, Stéphane Durocher, Bahoo, Yeganeh +5
Computer Science · Engineering · #3D Modeling in Geospatial Applications #65D18 #68Q25 #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #I.3.5
paper · pdf · doi:10.48550/arxiv.1702.08380
openalex publication_date 2017/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A straight-line drawing Γ 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 Γ 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 Γ 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 Γ, it is NP-complete to determine whether Γ contains an increasing-chord spanning tree rooted at r. We conjecture that finding an increasing-chord path between a pair of vertices in Γ, 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.