Pach, János and Saghafian, Morteza and Schnider, Patrick (2025) Decomposition of geometric graphs into star-forests. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 129. No.-102186. ISSN 0925-7721
|
Text
1-s2.0-S0925772125000240-main.pdf - Published Version Download (643kB) | Preview |
Official URL: https://doi.org/10.1016/j.comgeo.2025.102186
Abstract
We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n−1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs. © 2025
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Graph theory; STARS; Graph decomposition; Geometric graphs; Geometric graphs; Graph decompositions; Non-crossing edges; Convex geometric graphs; Star forests; Star forest; Graph thickness; Graph thickness; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 13 Jul 2025 06:49 |
| Last Modified: | 13 Jul 2025 06:49 |
| URI: | https://real.mtak.hu/id/eprint/221003 |
Actions (login required)
 |
Edit Item |
