Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs
<|reference_start|>Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs: 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 $\Theta(\sqrt{n})$.<|reference_end|>
@article{dumitrescu2024partitioning,
    title={Partitioning Complete Geometric Graphs on Dense Point Sets into Plane
  Subgraphs},
    author={Adrian Dumitrescu and J'anos Pach},
    journal={arXiv preprint arXiv:2405.17172},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.17172},
    primaryClass={math.CO cs.DM}
}