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 k-sector ordered Yao 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 ≥ 6, and provide some estimates for the remaining values of k. Namely, we show that d$_1$ (n) = Θ(logn); $\frac{1}{2}$ (n − 1) ≤ d$_3$ (n) ≤ 5⌈︁$\frac{n}{6}$⌉︁− 1; $\frac{2}{3}$ (n − 1) ≤ d$_5$(n) ≤ 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) =⌈︂$\frac{k}{2}$⌉︂· 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$. ... mehrThen ⌈$\frac{k}{2}$⌉≤ w$_k$ ≤⌈$\frac{k}{2}$⌉+ 1.

All the orders mentioned above can be constructed effectively