Construction and Local Routing for Angle-Monotone Graphs - Lubiw, Anna; Mondal, Debajyoti (Journal of Graph Algorithms and Applications, 2019)
A geometric graph in the plane is angle-monotone of width γ if every pair of vertices is connected by an angle-monotone path of width γ, a path such that the angles of any two edges in the path differ by at most γ. Angle-monotone graphs have good spanning properties. We prove that every point set in the plane admits an angle-monotone graph of width 90^°, hence with spanning ratio 2, and a subquadratic number of edges. This answers an open question posed by Dehkordi, Frati and Gudmundsson. We show how to construct, for any point set of size n and any angle α, 0 < α < 45^°, an angle-monotone graph of width (90^°+α) with O(nα) edges. Furthermore, we give a local routing algorithm to find angle-monotone paths of width (90^°+α) in these graphs. The routing ratio, which is the ratio of path length to Euclidean distance, is at most 1/(45^° + α2), i.e., ranging from 2 ≈ 1.414 to 2.613. For the special case α = 30^°, we obtain the full-Θ_6-graph and our routing algorithm achieves the known routing ratio 2 while finding angle-monotone paths of width 120^°.