Maximizing the Maximum Degree in Ordered Yao Graphs
<|reference_start|>Maximizing the Maximum Degree in Ordered Yao Graphs: For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Yao graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of $n$ points in $\mathbb{R}^d$, there exists an order such that the corresponding ordered Yao graph has maximum degree at least $\log{n}/(4d)$. Apart from the $1/(4d)$ factor, this bound is the best possible. As for the abstract setting, we show that for every $n$-element metric space, there exists an order such that the corresponding ordered Yao graph has maximum degree $\Omega(\sqrt{\log{n}/\log\log{n}})$.<|reference_end|>
@article{ágoston2024maximizing,
    title={Maximizing the Maximum Degree in Ordered Yao Graphs},
    author={P'eter 'Agoston, Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet
  Singh, Ji Zeng},
    journal={arXiv preprint arXiv:2406.08913},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.08913},
    primaryClass={math.CO cs.CG math.MG}
}