Ordered Yao graphs: maximum degree, edge density, and clique numbers

For a positive integer $k$ and an ordered set of $n$ points in the plane, define its $\mathit{\text{k-sector}}\mathit{\text{ordered}}\mathit{\text{Yao}}\mathit{\text{graphs}}$ as follows. Divide the plane around each point into $k$ equal sectors and draw an edge from each point to its closest predecessor in each of the $k$ sectors. We analyze several natural parameters of these graphs. Our main results are as follows: I Let $d_k(n)$ be the maximum integer so that for every $n$-element point set in the plane, there exists an order such that the corresponding $k$-sector ordered Yao graph has maximum degree at least $d_k(n)$. We show that $d_k(n)=n-1$ if $k=4$ or $k\ge 6$, and provide some estimates for the remaining values of $k$. Namely, we show that $d_1(n)=\mathrm{\Theta }(\log n)$; $\frac{1}{2}(n-1)\le d_3(n)\le 5\lceil \frac{n}{6}\rceil -1$; $\frac{2}{3}(n-1)\le d_5(n)\le n-1$; II Let $e_k(n)$ be the minimum integer so that for every $n$-element point set in the plane, there exists an order such that the corresponding $k$-sector ordered Yao graph has at most $e_k(n)$ edges. Then $e_k(n)=\lceil \frac{k}{2}\rceil \cdot n-o(n)$. III Let $w_k$ be the minimum integer so that for every point set in the plane, there exists an order such that the corresponding $k$-sector ordered Yao graph has clique number at most $w_k$. Then $\lceil \frac{k}{2}\rceil \le w_k\le \lceil \frac{k}{2}\rceil +1$. All the orders mentioned above can be constructed effectively.