























A \emph{complete geometric graph} consists of a set $P$ of $n$ points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant $c<1$, such that every complete geometric graph on $n$ points can be partitioned into at most $cn$ plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set $P$ is \emph{dense}, which means that the ratio between the maximum and the minimum distances in $P$ is of the order of $Θ(\sqrt{n})$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。