Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00494
Construction and Local Routing for AngleMonotone Graphs
Vol. 23, no. 2, pp. 345369, 2019. Regular paper.
Abstract A geometric graph in the plane is anglemonotone of width $\gamma$ if every pair of vertices is connected by an anglemonotone path of width $\gamma$, a path such that the angles of any two edges in the path differ by at most $\gamma$. Anglemonotone graphs have good spanning properties.
We prove that every point set in the plane admits an anglemonotone graph of width $90^\circ$, hence with spanning ratio $\sqrt 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 $\alpha$, $0 < \alpha < 45^\circ$, an anglemonotone graph of width $(90^\circ+\alpha)$ with $O(\frac{n}{\alpha})$ edges.
Furthermore, we give a local routing algorithm to find anglemonotone paths of width $(90^\circ+\alpha)$ in these graphs.
The \emph{routing ratio}, which is the ratio of path length to Euclidean distance, is at most $1/\cos(45^\circ + \frac{\alpha}{2})$, i.e., ranging from $\sqrt 2 \approx 1.414$ to $2.613$. For the special case $\alpha = 30^\circ$, we obtain the full$\Theta_6$graph and our routing algorithm achieves the known routing ratio 2 while finding anglemonotone paths of width $120^\circ$.

Submitted: October 2018.
Reviewed: February 2019.
Revised: April 2019.
Accepted: April 2019.
Final: April 2019.
Published: April 2019.
Communicated by
Giuseppe Liotta

Journal Supporters
