Dumitrescu, A. and Pach, János (2024) Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs. In: Leibniz International Proceedings in Informatics, LIPIcs. Leibniz International Proceedings in Informatics, LIPIcs (320). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 9. ISBN 9783959773430
|
Text
2405.17172v2.pdf Download (581kB) | Preview |
Abstract
A 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 dense, which means that the ratio between the maximum and the minimum distances in P is of the order of Θ(√ n). © Adrian Dumitrescu and János Pach.
| Item Type: | Book Section |
|---|---|
| Additional Information: | Algoresearch L.L.C., Milwaukee, WI, United States Alfréd Rényi Institute of Mathematics, Budapest, Hungary EPFL, Lausanne, Switzerland Export Date: 30 December 2024; Cited By: 0; Correspondence Address: ; ; Conference name: 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024; Conference date: 18 September 2024 through 20 September 2024; Conference code: 203623 |
| Uncontrolled Keywords: | GEOMETRY; Graph theory; Convexity; Convexity; Subgraphs; Graphic methods; Geometric graphs; Noncrossing; Crossing family; Crossing family; Point set; Positive constant; Plane graphs; Plane subgraph; Plane subgraph; complete geometric Graph; Complete geometric graph; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 31 Dec 2024 05:18 |
| Last Modified: | 31 Dec 2024 05:18 |
| URI: | https://real.mtak.hu/id/eprint/212579 |
Actions (login required)
 |
Edit Item |
