d. bakhshesh

For $0<\gamma<180^{\circ}$, a geometric path $P=(p_1,\ldots, p_n)$ is called angle-monotone with width $\gamma$ from $p_1$ to $p_n$ if there exists a closed wedge of angle $\gamma$ such that every directed edge $\overrightarrow{p_ip_{i+1}}$ of~$P$ lies inside the wedge whose apex is $p_i$. A geometric graph $G$ is called angle-monotone with width $\gamma$ if for any two vertices $p$ and $q$ in $G$, there exists an angle-monotone path with width $\gamma$ from $p$ to $q$. In this paper, we show that for any integer $k\geq 1$ and any $i\in\{2, 3, 4, 5\}$, the theta-graph $\Theta_{4k+i}$ on a set of points in convex position is angle-monotone with width $90^\circ+\frac{i\theta}{4}$, where $\theta=\frac{360^{\circ}}{4k+i}$. Moreover, we present two sets of points in the plane, one in convex position and the other in non-convex position, to show that for every $0<\gamma<180^\circ$, the graph $\Theta_4$ is not angle-monotone with width $\gamma$.

One of the most popular graphs in computational geometry is Yao graphs, denoted by $Y_k$, For every point set $S$ in the plane and an integer $k\geq 2$, the Yao graph $Y_k$ is constructed as follows. Around each point $p\in S$, the plane is partitioned into $k$ regular cones with the apex at $p$. The set of all these cones is denoted by ${\cal C}_p$. Then, for each cone $C\in {\cal C}_p$, an edge $(p,r)$ is added to $Y_k$, where $r$ is a closest point in $C$ to $p$. In this paper, we provide a lower bound of 3.8285 for the stretch factor of $Y_4$. This partially solves an open problem posed by Barba et al. (L.~Barba et al., New and improved spanning ratios for Yao graphs. Journal of computational geometry}, 6(2):19--53, 2015).

Let $S$ be a set of $n$ points in the plane that is in convex position. In this paper, using the well-known path-greedy spanner algorithm, we present an algorithm that constructs a plane $frac{3+4pi}{3}$-spanner $G$ of degree 3 on the point set $S$. Recently, Biniaz et al. ({it Towards plane spanners of degree 3, Journal of Computational Geometry, 8 (1), 2017}) have proposed an algorithm that constructs a degree 3 plane $frac{3+4pi}{3}$-spanner $G'$ for $S$. We show that there is no upper bound with a constant factor on the total weight of $G'$, but the total weight of $G$ is asymptotically equal to the total weight of the minimum spanning tree of $S$.