Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914917426135040 |
|---|---|
| author | Dumitrescu, Adrian Pach, János |
| author_facet | Dumitrescu, Adrian Pach, János |
| contents | 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})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17172 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs Dumitrescu, Adrian Pach, János Combinatorics Discrete Mathematics 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})$. |
| title | Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.17172 |